这道题还是挺好想的，但我一开始还是想错了……
把每个石柱拆成两个点，一个入度，一个出度，两个点连一条容量为高度的边，这样就可以限制从此石柱上经过的蜥蜴的数量。关于蜥蜴是否单独成点，我是单独当成了一个点，貌似做麻烦了，可以直接源点连石柱，但那样我想会不会造成一些问题，貌似也没有。
虽然很水，但还是调了很久。主要问题出在建图上，我把一个点拆成了高度个点，这样无法达到上面说的限制蜥蜴经过的数量这个功能，所以ＷＡ了很久，看了题解，才突然明白，这么搞不行……
代码如下：
#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());
}
