? ? 這道題還是挺好想的，但我一開始還是想錯了……
? ? 把每個石柱拆成兩個點，一個入度，一個出度，兩個點連一條容量為高度的邊，這樣就可以限制從此石柱上經過的蜥蜴的數量。關于蜥蜴是否單獨成點，我是單獨當成了一個點，貌似做麻煩了，可以直接源點連石柱，但那樣我想會不會造成一些問題，貌似也沒有。
? ? 雖然很水，但還是調了很久。主要問題出在建圖上，我把一個點拆成了高度個點，這樣無法達到上面說的限制蜥蜴經過的數量這個功能，所以ＷＡ了很久，看了題解，才突然明白，這么搞不行……
? ? 代碼如下：
#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());
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
