HDU-2732-Leapin' Lizards（最大流，拆点，Dinic，弧优化）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2732

题目大意：T组测试数据，每组测试数据输入 n（n行的地图）没有m，需要自己找，再给一个D，一只蜥蜴行走的最远距离， 再给出两个图，分别是某个位置所能行走的次数，后面的那个图是蜥蜴的初始位置，看蜥蜴们能不能逃出这个地图（出地图边界）

很明显的拆点，一个平台分成两半，自己与自己联通的是流量限制，与其他联通的是INF；

下面的图给的是与 源 的连线；

能直接跳出来的与 汇 直接连；

一般难度拆点题：我感觉用上弧优化会更快一点，但是看时间，似乎不用弧优化也可以过，但我没试

ac;

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<fstream>
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 998244353
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
struct dot{
	int x,y;
}d[100010];
struct node{
	int v,w,cost,nxt;
	node(int _v=0,int _w=0,int _nxt=0):
    v(_v),w(_w),nxt(_nxt){}
}edge[500005<<1];
int head[500005],cur[500005],ecnt;
int dis[500005];
int n,m,s,t;
int D,sum;
void intt()
{
	clean(head,-1);
	clean(cur,-1);
	ecnt=0;
	s=0,t=801;
}
void add(int u,int v,int w)
{
	edge[ecnt]=node(v,w,head[u]);
	head[u]=ecnt++;
	edge[ecnt]=node(u,0,head[v]);
	head[v]=ecnt++;
}
/*---上面的是板子，不用动---*/

bool bfs()
{
	clean(dis,-1);
	dis[s]=0;
	queue<int> que;
	que.push(s);
	while(que.size())
	{
		int u=que.front();
		que.pop();
		if(u==t)
			return 1; 
		for(int i=head[u];i+1;i=edge[i].nxt)
		{
			int temp=edge[i].v;
			if(dis[temp]==-1&&edge[i].w>0)
			{
				dis[temp]=dis[u]+1;
				que.push(temp);
			}
		}
	}
	return 0;
}

int dfs(int u,int low)
{
	if(u==t||low==0)
		return low;
	int res=0;
	for(int &i=cur[u];i+1;i=edge[i].nxt)
	{
		int temp=edge[i].v;
		if(dis[temp]==dis[u]+1&&edge[i].w>0)
		{
			int f=dfs(temp,min(low-res,edge[i].w));
			edge[i].w-=f;
			edge[i^1].w+=f;
			res=res+f;
			if(res==low)
				break;
		}
	}
	return res;
}

int dinic()
{
	int ans=0,res;
	while(bfs())
	{
		for(int i=s;i<=t;++i)
			cur[i]=head[i];
		ans=ans+dfs(s,INF);
	}
	return ans;
}

int main()
{
	int T,Cas=1;
	cin>>T;
	while(T--)
	{
		intt();
		cin>>n>>D;
		sum=0;
		string str;
		for(int i=1;i<=n;++i)//读入次数 
		{
			cin>>str;
			if(i==1)
				m=str.size();
			int len=m;
			for(int j=0;j<len;++j)
			{
				if(str[j]-'0'>0)
				{
					int u=(i-1)*m+j+1;
					add(u,u+400,str[j]-'0');//拆点 
					if(i-D<=0||i+D>n||j-D<0||j+D>=m)
						add(u+400,t,INF);//直接跳出地图 
					else
					{
						for(int k=1;k<=n;++k)
						{
							for(int h=0;h<m;++h)
							{
								int u2=(k-1)*m+h+1;
								if(u==u2)
									continue;
								if(abs(i-k)+abs(j-h)<=D)
									add(u+400,u2,INF);
							}
						}
					}
				}
			}
		}
		for(int i=1;i<=n;++i)//读入柱子 
		{
			cin>>str;
			for(int j=0;j<m;++j)
			{
				int u=(i-1)*m+j+1;
				if(str[j]=='L')
				{
					++sum;//加一只蜥蜴
					add(s,u,1);
				}
			}
		}
//		for(int i=s;i<=t;++i)//图没错 
//		{
//			cout<<i<<" : ";
//			for(int j=head[i];j+1;j=edge[j].nxt)
//				cout<<edge[j].v<<" "<<edge[j].w<<" ->>";
//			cout<<endl;
//		}
		
		int ans=sum-dinic();
		//cout<<ans<<" "<<sum-ans<<endl;
		if(ans==0)
			cout<<"Case #"<<Cas++<<": no lizard was left behind."<<endl;
		else if(ans==1)
			cout<<"Case #"<<Cas++<<": 1 lizard was left behind."<<endl;
		else
			cout<<"Case #"<<Cas++<<": "<<ans<<" lizards were left behind."<<endl;
	}
}