hdu 2732最大流

この問題は点を分解することであり,各点の容量制限を与え,各点がescapeであれば集点連条inf,各点が届く柱連条inf,ソース点がlizardのある場所連条長が1の辺,ansがsum(lizard)-最大流である

#include<cstdio>
#include<cstring>
int T,n,d,m,cnt,dis[1000],gap[1000],head[1000],s,t,sum,N;
const int inf=10000000;
struct EDGE
{
	int to,f,nxt;
}edge[300000];
char g[30][30],gg[30][30],x[30][30];
int dx[]={1,1,-1,-1};
int dy[]={1,-1,1,-1};
int min(int a,int b)
{
	return a<b?a:b;
}
void add(int x,int y,int c)
{
	edge[cnt].to=y;
	edge[cnt].f=c;
	edge[cnt].nxt=head[x];
	head[x]=cnt++;
}
void gao(int x,int y,int c)
{
	add(x,y,c);
	add(y,x,0);
}
int safe(int a,int b)
{
	return a-d<=0||a+d>=n+1||b-d<=0||b+d>=m+1;
}
int in(int a,int b)
{
	return a>=1&&a<=n&&b>=1&&b<=m;
}
void init()
{
	memset(head,-1,sizeof(head));
	memset(dis,0,sizeof(dis));
	memset(gap,0,sizeof(gap));
	sum=cnt=0;
}
int dfs(int x,int flow)
{
	if(x==t)
	return flow;
	int temp=flow;
	int pos=t-1;
	int j;
	for(j=head[x];j!=-1;j=edge[j].nxt)
	{
		int y=edge[j].to;
		int c=edge[j].f;
		if(c>0&&dis[x]==dis[y]+1)
		{
			int temp_flow=dfs(y,min(temp,c));
			temp-=temp_flow;
			edge[j].f-=temp_flow;
			edge[j^1].f+=temp_flow;
			if(temp==0||dis[s]==t)
			return flow-temp;
		}
		if(c>0&&pos>dis[y])
		pos=dis[y];
	}
	if(temp==flow)
	{
		if(!(--gap[dis[x]]))
		dis[s]=t;
		else
		gap[dis[x]=pos+1]++;
	}
	return flow-temp;
}
int sap()
{
	int maxflow=0;
	gap[0]=t;
	while(dis[s]<t)
	{
		maxflow+=dfs(s,inf);
	}
	return sum-maxflow;
}
int main()
{
	int pro=0;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&d);
		init();
		for(int i=1;i<=n;i++)
			scanf("%s",g[i]+1);
		m=strlen(g[1]+1);
		N=n*m;
		s=2*N+1,t=s+1;
		for(int i=1;i<=n;i++)
			scanf("%s",gg[i]+1);
		int k1=0,k2=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int num=(i-1)*m+j;
			if(safe(i,j))
			gao(num+N,t,inf);
			if(g[i][j]-'0')
			gao(num,num+N,g[i][j]-'0');
		}
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(gg[i][j]=='L')
			{
				int num=(i-1)*m+j;
				sum++;
				gao(s,num,1);
			}
		}
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int num=(i-1)*m+j;
			for(int z=0;z<4;z++)
			for(int k1=0;k1<=d;k1++)
			for(int k2=0;k2<=d;k2++)
			if(k1+k2>0&&k1+k2<=d)
			{
				int x=i+k1*dx[z];
				int y=j+k2*dy[z];
				int mun=(x-1)*m+y;
				if(in(x,y))
				gao(num+N,mun,inf);
			}
		}
		int ans=sap();
		if(ans>1)printf("Case #%d: %d lizards were left behind.
",++pro,ans);  
        else if(ans)printf("Case #%d: %d lizard was left behind.
",++pro,ans);  
        else printf("Case #%d: no lizard was left behind.
",++pro);  
	}
	return 0;
}