求助
查看原帖
求助
210915
bluedoor418楼主2022/1/12 17:52

孩子快调疯了。。一直是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;
}
2022/1/12 17:52
加载中...