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

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）