孩子快调疯了。。一直是28分,不知道是哪里错了,有人能帮忙看看吗
#include<bits/stdc++.h>
#define MAXN 2000001
#define inf 0x3f3f3f3f
using namespace std;
int head[MAXN],ver[MAXN],edge[MAXN],Next[MAXN],tot=1;
inline void add(int x,int y,int z)
{
ver[++tot]=y;edge[tot]=z;
Next[tot]=head[x];head[x]=tot;
return;
}
inline void add_edge(int x,int y,int z)
{
add(x,y,z);
add(y,x,0);
return;
}
int a[MAXN];
int s=500001,t=500010;
int sz;
int r,c,d;
char str[MAXN];
inline int code(int i,int j)
{
return (i-1)*c+j;
}
inline double d_find(int i,int j,int ii,int jj)
{
return sqrt((i-ii)*(i-ii)+(j-jj)*(j-jj));
}
int dis[MAXN];
inline int bfs()
{
memset(dis,0,sizeof(dis));
queue <int> q;
q.push(s);
dis[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(!dis[y]&&edge[i])
{
dis[y]=dis[x]+1;
q.push(y);
}
}
}
return dis[t];
}
inline int dfs(int x,int flow)
{
if(x==t) return flow;
int out=0,res;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(edge[i]&&dis[y]==dis[x]+1)
if((res=dfs(y,min(flow,edge[i])))>0)
{
out+=res;
flow-=res;
edge[i]-=res;
edge[i^1]+=res;
}
if(!flow) break;
}
if(!out) dis[x]=0;
return out;
}
int sum=0;
inline void read()
{
scanf("%d%d%d",&r,&c,&d);
for(int i=1;i<=r;i++)
{
cin>>(str+1);
for(int j=1;j<=c;j++)
a[code(i,j)]=str[j]-'0';
}
sz=r*c;
for(int i=1;i<=r;i++)
{
cin>>(str+1);
for(int j=1;j<=c;j++)
if(str[j]=='L'&&a[code(i,j)])
{
sum++;
add_edge(s,code(i,j),1);
}
}
return;
}
inline void build()
{
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
add_edge(code(i,j),code(i,j)+sz,a[code(i,j)]);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
if(!a[code(i,j)]) continue;
if(i<=d||j<=d)
add_edge(code(i,j)+sz,t,inf);
for(int ii=i-d;ii<=i+d&&ii<=r;ii++)
for(int jj=j-d;jj<=j+d&&jj<=c;jj++)
if(a[code(ii,jj)]&&(!(ii==i&&jj==i)))
if(d_find(i,j,ii,jj)<=(double)d)
add_edge(code(ii,jj)+sz,code(i,j),inf);
}
return;
}
int main()
{
read();
build();
int ans=0;
while(bfs())
ans+=dfs(s,(1<<30));
cout<<(sum-ans);
return 0;
}