理解不够透彻。好题不可浪费，写题解以增进理解。会陆续补充题目。（咕咕咕）

G Beihang Couple Pairing Comunity 2017

题目链接

Beihang Couple Pairing Comunity 2017

解题思路

第一步：分析题目

首先，如果只判断是否有Poor single dog，这是一道DFS入门题。于是DFS搜一遍，把每个点与出口的距离（DFS距离）表示出来并存储。

一对人拆开没有任何优化，所以看成一个人即可。

这里用到几个变换：

\(state[i][j]\)，表示\((i,j)\)这个点上面是墙，是出口，还是人；

\(e[i]\)，表示第几个出口的坐标；\(cnt1\)，记录有几个出口；\(num[i][j]\)，记录这个\((i,j)\)对应的\(e[i]\)中\(i\)的值；

\(p[i]\)，表示第几对人的坐标；\(cnt2\)，记录有几对人；\(num[i][j]\)，记录这个\((i,j)\)对应的\(p[i]\)中\(i\)的值。

第二步：模型建立

\(1.\)很明显，这个题可以建图用网络流求解。（事实证明可以用二分图做而且更简单）

原因有三：

一是数据范围小，连边可行

二是点与点、出口与点之间存在某种制约关系，而这种制约关系能够通过图很好地体现

三是这种制约关系可以通过建图体现，而通过网络流求解。

\(2.\)可以想到，可以二分答案。

原因有二：

一是答案具有单调性，因为时间越长越有可能让更多对人逃离，而时间越短越是正解。如果不明白（都会网络流了还不会二分答案似乎不太可能）请点击这里。

二是如果用网络流求解，只能判断某个时间的可行性，故（我认为）不可直接解出。（如果有直接一步网络流的解法请务必联系我）

焦点在于，如何建图。

首先很容易想到的是将源点\(S\)和每一个点\((.)\)连边，每一个点和（与他距离不超过\(mid\)的）（\(mid\)是二分答案的那个\(mid\)）出口\((E)\)连边，所有出口和汇点\(T\)连边。

这样连边之后，跑网络流，能够得到WA。

这是为什么呢？

原因在于，只考虑了连边的可行性，而忽视了连边需要考虑的另一个因素：从这个点跑到这个出口的最小时间。

也就是说，需要把时间纳入连边的考虑内。

如何纳入考虑？

很自然地想到了拆点。每一个出口对应一个出去的时间，在每一秒里只可以通过一对人，所以可以把一个出口拆成\(mid\)个出口，其中第\(i\)个出口\(E_i\)表示这个出口在时间\(i\)的时候的状态。

于是，综上所述，源S和每一个点\((.)\)连边，每一个点和从\(E_{matrix[i][j]}\)到\(E_{mid}\)的\(E\)连边，每一个拆出来的出口和\(T\)连边。

第三步：写出伪代码

深搜：（比较简单直接码）

void dfsearch(int fir,int x,int y,int dep){

	int i;

	if(x<0||y<0||x>=n||y>=m)return;

	if(vis[x][y]<=dep)return;

	vis[x][y]=dep;

	if(!state[x][y])return;//墙

	if(state[x][y]==1){

		if(dep<matrix[fir][number[x][y]])matrix[fir][number[x][y]]=dep;

		else return;//必然无法增广更优路线

	}

	dfsearch(fir,x+1,y,dep+1);

	dfsearch(fir,x-1,y,dep+1);

	dfsearch(fir,x,y-1,dep+1);

	dfsearch(fir,x,y+1,dep+1);

}

Main：

int main(){

	scanf("%d",&T);

	while(T--){

		//initialization

		scanf("%d%d",&n,&m);

		for(i=0;i<n;i++){

			scanf("%s",a);

			for(j=0;j<m;j++){

				if(a[j]=='X')state[i][j]=0;

				else if(a[j]=='E')state[i][j]=1,e[cnt1].x=i,e[cnt1].y=j,number[i][j]=cnt1,cnt1++;

				else state[i][j]=2,p[cnt2].x=i,p[cnt2].y=j,number[i][j]=cnt2,cnt2++;

			}

		}

		//DFS:先判断有没有出不去的，同时fill matrix

		for(i=0;i<cnt2;i++){

			memset(vis,inf,sizeof(vis));

			dfsearch(i,p[i].x,p[i].y,0);

			int flag=0;

			for(j=0;j<cnt1;j++)if(matrix[i][j]<inf){

				flag=1;break;

			}

			if(!flag){

				//输出;

				//继续下一轮读入

			}

		}

		//再二分答案，判断mid可行不可行

		int left=1,right=cnt2;

		while(left<right){

			int mid=left+right>>1;

			//跑最大流=点数，可行

			//建图

			//跑最大流，如果没有全覆盖（最大流小于点数），则left=mid+1，否则right=mid

		}

		printf("%d\n",left);

	}

	return 0;

}

这就结束了。具体细节比如点的下标如何分配不再赘述。

\(Dinic\)别忘加当前弧优化，否则会\(T\)。

AC代码

#include<stdio.h>

#include<string.h>

int state[23][23],n,m;//2人0墙1出口

int number[23][23];

int matrix[402][402];//i:cnt2人，j:cnt1出口

int inf=100000000;

struct Position{

	int x,y;

}p[402],e[402];

int cnt1,cnt2;

int s=1,t=2;

int head[320005],cnt=2;

int queue[320005],depth[320005];

int cur[320005];

struct Edge{

	int end,len,near;

}edge[32000010];

void add(int begin,int end,int len){

	edge[cnt].end=end;

	edge[cnt].len=len;

	edge[cnt].near=head[begin];

	head[begin]=cur[begin]=cnt;

	cnt++;

}

int dfs(int,int);

int bfs();

int dinic();

int vis[1010][1010];

void dfsearch(int fir,int x,int y,int dep);

int f(int x,int y,int mid){return cnt2+x*mid+y;}

int min(int a,int b){return a>b?b:a;}

int main(){

	int i,j,T,k;

	char a[100]={0};

	scanf("%d",&T);

	while(T--){

		cnt1=cnt2=0;

		memset(matrix,0x3f,sizeof(matrix));

		scanf("%d%d",&n,&m);

		for(i=0;i<n;i++){

			scanf("%s",a);

			for(j=0;j<m;j++){

				if(a[j]=='X')state[i][j]=0;

				else if(a[j]=='E')state[i][j]=1,e[cnt1].x=i,e[cnt1].y=j,number[i][j]=cnt1,cnt1++;

				else state[i][j]=2,p[cnt2].x=i,p[cnt2].y=j,number[i][j]=cnt2,cnt2++;

			}

		}

		//先判断有没有出不去的，同时fill matrix

		for(i=0;i<cnt2;i++){//人

			memset(vis,0x3f,sizeof(vis));

			dfsearch(i,p[i].x,p[i].y,0);

			int flag=0;

			for(j=0;j<cnt1;j++)if(matrix[i][j]<inf){

				flag=1;break;

			}

			if(!flag){

				printf("Oh, poor single dog!\n");

				break;

			}

		}

		if(!flag)continue;

		//再二分答案，判断mid可行不可行

		int left=1,right=cnt2;

		while(left<right){

			int mid=left+right>>1;

			//跑最大流=点数，可行

			cnt=2;

			memset(head,0,sizeof(head));

			memset(cur,0,sizeof(cur));

			for(i=0;i<cnt2;i++){

				for(j=0;j<cnt1;j++){

					if(matrix[i][j]<=mid){//人->E

						for(k=matrix[i][j];k<=mid;k++){

							add(f(j,k,mid),i+3,0);

							add(i+3,f(j,k,mid),1);

						}

					}

				}

				add(i+3,s,0);//源->人

				add(s,i+3,1);

			}

			for(i=0;i<cnt1;i++){

				for(j=1;j<mid;j++){

					add(f(i,j,mid),f(i,j+1,mid),1);

					add(f(i,j+1,mid),f(i,j,mid),0);

					add(f(i,j,mid),t,1);

					add(t,f(i,j,mid),0);

				}

				add(f(i,mid,mid),t,1);

				add(t,f(i,mid,mid),0);

			}

			int din=dinic();

			if(din<cnt2)left=mid+1;

			else right=mid;

		}

		printf("%d\n",left);

	}

	return 0;

}

void dfsearch(int fir,int x,int y,int dep){

	int i;

	if(x<0||y<0||x>=n||y>=m)return;

	if(vis[x][y]<=dep)return;

	vis[x][y]=dep;

	if(!state[x][y])return;//墙

	if(state[x][y]==1){

		if(dep<matrix[fir][number[x][y]])matrix[fir][number[x][y]]=dep;

		else return;//必然无法增广更优路线

	}

	dfsearch(fir,x+1,y,dep+1);

	dfsearch(fir,x-1,y,dep+1);

	dfsearch(fir,x,y-1,dep+1);

	dfsearch(fir,x,y+1,dep+1);

}

int dinic(){

	int ans=0,p,i;

	while(bfs()){

		while((p=dfs(s,inf)))ans+=p;

		for(i=0;i<160000;i++)cur[i]=head[i];

	}

	return ans;

}

int bfs(){

	memset(queue,0,sizeof(queue));

	memset(depth,0,sizeof(depth));

	int hd=0,tl=0;

	queue[tl++]=s;

	depth[s]=1;

	while(hd<tl){

		int i;

		for(i=head[queue[hd]];i;i=edge[i].near){

			int p=edge[i].end;

			if(edge[i].len&&!depth[p]){

				depth[p]=depth[queue[hd]]+1;

				queue[tl++]=p;

			}

		}

		hd++;

	}

	return depth[t];

}

int dfs(int p,int flow){

	if(p==t)return flow;

	int i;

	for(i=cur[p];i;i=edge[i].near){

		cur[p]=i;

		int k=edge[i].end;

		if(depth[k]==depth[p]+1&&edge[i].len){

			int ans=dfs(k,min(flow,edge[i].len));

			if(ans){

				edge[i].len-=ans;

				edge[i^1].len+=ans;

				return ans;

			}

		}

	}

	return 0;

}

（在正解的基础上有不影响整体代码结构的修改，交上并不能AC）

巴特西

2017算法期末复习练习赛-G Beihang Couple Pairing Comunity 2017 题解（网络流）