? ? 這道題還是挺好想的，但我一開(kāi)始還是想錯(cuò)了……
? ? 把每個(gè)石柱拆成兩個(gè)點(diǎn)，一個(gè)入度，一個(gè)出度，兩個(gè)點(diǎn)連一條容量為高度的邊，這樣就可以限制從此石柱上經(jīng)過(guò)的蜥蜴的數(shù)量。關(guān)于蜥蜴是否單獨(dú)成點(diǎn)，我是單獨(dú)當(dāng)成了一個(gè)點(diǎn)，貌似做麻煩了，可以直接源點(diǎn)連石柱，但那樣我想會(huì)不會(huì)造成一些問(wèn)題，貌似也沒(méi)有。
? ? 雖然很水，但還是調(diào)了很久。主要問(wèn)題出在建圖上，我把一個(gè)點(diǎn)拆成了高度個(gè)點(diǎn)，這樣無(wú)法達(dá)到上面說(shuō)的限制蜥蜴經(jīng)過(guò)的數(shù)量這個(gè)功能，所以ＷＡ了很久，看了題解，才突然明白，這么搞不行……
? ? 代碼如下：
#include <cstdio>
#include
<cstring>
#include
<cstdlib>
#include
<iostream>
#include
<algorithm>
#include
<queue>
#define
N 25
#define
inf 1<<30
using
namespace
std;
struct
sss
{
int
x,y;
}xiyi[N
*
N];
int
n,m,S,T,d;
int
a[N][N]={
0
},num[N][N]={
0
},stonenum=
0
,xiyinum=
0
;
int
p[N*N*
5
],next[N*N*N*N*
6
],v[N*N*N*N*
6
],f[N*N*N*N*
6
],bnum=-
1
;
bool
kexing(
int
x,
int
y)
{
if
(x<
1
||x>n||y<
1
||y>m)
return
false
;
else
return
true
;
}
void
addbian(
int
x,
int
y,
int
flow)
{
bnum
++; next[bnum]=
p[x];
p[x]
=bnum; v[bnum]=y; f[bnum]=
flow;
bnum
++; next[bnum]=
p[y];
p[y]
=bnum; v[bnum]=x; f[bnum]=
0
;
}
int
dis[N*N*
5
];
bool
BFS()
{
int
i,j,k;
queue
<
int
>
q;
for
(i=
1
;i<=T;i++) dis[i]=-
1
;
dis[S]
=
0
; q.push(S);
while
(!
q.empty())
{
j
=q.front(); q.pop(); k=
p[j];
while
(k!=-
1
)
{
if
(f[k]&&dis[v[k]]==-
1
)
{
dis[v[k]]
=dis[j]+
1
;
q.push(v[k]);
}
k
=
next[k];
}
}
if
(dis[T]==-
1
)
return
false
;
else
return
true
;
}
int
DFS(
int
now,
int
change)
{
int
i,j,k,flow=
0
;
if
(now==T||change==
0
)
return
change;
k
=
p[now];
while
(k!=-
1
)
{
if
(f[k]&&dis[v[k]]==dis[now]+
1
&&(i=DFS(v[k],min(change,f[k])))>
0
)
{
f[k]
-=i; f[k^
1
]+=
i;
flow
+=i; change-=
i;
if
(change==
0
)
break
;
}
k
=
next[k];
}
dis[now]
=-
1
;
return
flow;
}
int
dinic()
{
int
ans=
0
,flow;
while
(BFS())
while
(flow=
DFS(S,inf))
ans
+=
flow;
return
ans;
}
bool
bianjie(
int
x,
int
y)
{
if
(x<=d||y<=d)
return
true
;
else
if
(n-x<d||m-y<d)
return
true
;
else
return
false
;
}
int
main()
{
int
i,j,k,x,y;
char
s[N];
scanf(
"
%d%d%d
"
,&n,&m,&
d);
S
=n*m*
3
+
1
; T=n*m*
3
+
2
;
for
(i=
1
;i<=T;i++) p[i]=-
1
;
for
(i=
1
;i<=n;i++
)
{
scanf(
"
%s
"
,s);
for
(j=
0
;j<m;j++
)
if
(s[j]!=
'
0
'
) a[i][j+
1
]=s[j]-
'
0
'
;
}
for
(i=
1
;i<=n;i++
)
{
scanf(
"
%s
"
,s);
for
(j=
0
;j<m;j++
)
if
(s[j]==
'
L
'
)
{
xiyinum
++; a[i][j+
1
]--
;
xiyi[xiyinum].x
=i; xiyi[xiyinum].y=j+
1
;
}
}
for
(i=
1
;i<=n;i++
)
for
(j=
1
;j<=m;j++
)
if
(a[i][j]>
0
)
{
stonenum
++
;
num[i][j]
=
stonenum;
}
for
(i=
1
;i<=n;i++
)
for
(j=
1
;j<=m;j++
)
if
(a[i][j]>
0
)
{
addbian(num[i][j],num[i][j]
+n*
m,a[i][j]);
if
(bianjie(i,j))
addbian(num[i][j]
+n*
m,T,inf);
for
(
int
I=-d;I<=d;I++
)
for
(
int
J=-d;J<=d;J++
)
if
(!(I==
0
&&J==
0
)&& I*I+J*J<=d*
d)
{
x
=i+I; y=j+
J;
if
(kexing(x,y)&&
a[x][y])
addbian(num[i][j]
+n*
m,num[x][y],inf);
}
}
for
(i=
1
;i<=xiyinum;i++
)
{
int
x1=xiyi[i].x,y1=
xiyi[i].y;
addbian(S,i
+n*m*
2
,
1
);
if
(bianjie(x1,y1))
addbian(i
+n*m*
2
,T,inf);
for
(
int
I=-d;I<=d;I++
)
for
(
int
J=-d;J<=d;J++
)
if
(!(I==
0
&&J==
0
)&& I*I+J*J<=d*
d)
{
x
=x1+I; y=y1+
J;
if
(kexing(x,y)&&
a[x][y])
addbian(i
+n*m*
2
,num[x][y],inf);
}
}
printf(
"
%d\n
"
,xiyinum-
dinic());
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
