题解 P2691 【逃离】

· · 题解

第一眼看到这个题目

这不是最大流的经典题目吗

考虑建图

题目给了m个起点，显然我们要用一个超级源点把这些点连起来

得到yes的条件是 m个起点到边界有m条不重复的边，即如果网格中的每个点只走一遍，是否每个起始点都能走到边界

这样我们就可以把边界上的点都连到一个超级汇点上

每个点只能走一遍，可以把一个点拆成两个点，然后把容量设成1

这样跑一遍最大流，如果流量为m的话就说明每个起始点都能走到边界且路径不重复

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define inf 1<<30
#define maxn 2333
int n,m,k,head[maxn*maxn],lev[maxn*maxn],cur[maxn*maxn],tot=1,S,T,ans;
queue<int>que; bool vis[maxn][maxn];
struct Edge{
    int to,nxt,dis;
}e[maxn*maxn];
inline void add(int u,int v,int d)
{
    e[++tot].to=v; e[tot].nxt=head[u]; e[tot].dis=d; head[u]=tot;
    e[++tot].to=u; e[tot].nxt=head[v]; e[tot].dis=0; head[v]=tot;
}
inline void read(int &now)
{
    char ch=getchar(); now=0;
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar(); 
}
bool bfs()
{
    while(!que.empty()) que.pop();
    for(int i=S;i<=T;i++) lev[i]=-1,cur[i]=head[i];
    lev[S]=0; que.push(S);
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            if(e[i].dis>0&&lev[e[i].to]==-1)
            {
                lev[e[i].to]=lev[u]+1;
                que.push(e[i].to);
                if(e[i].to==T) return true;
            }
        }
    }
    return false;
}
int dinic(int u,int flow)
{
    if(u==T) return flow;
    int res=0,delta;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        if(e[i].dis>0&&lev[e[i].to]==lev[u]+1)
        {
            delta=dinic(e[i].to,min(e[i].dis,flow-res));
            e[i].dis-=delta; e[i^1].dis+=delta;
            res+=delta; if(res==flow) break;
        }
    }
    if(res!=flow) lev[u]=-1;
    return res;
}
int main()
{
    read(n);
    read(m);
    S=0; T=2*n*n+1,tot=0;
    for(int i=1;i<=n*n;i++) add(i,i+n*n,1);
    for(int i=1;i<=m;i++)
    {
        int x,y; read(x); read(y);
        add(S,n*(x-1)+y,1);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<n;j++)
        {
            add(n*n+n*(i-1)+j,n*(i-1)+j+1,1);
            add(n*n+n*(i-1)+j+1,n*(i-1)+j,1);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=n;j++)
        {
            add(n*n+n*(i-1)+j,n*i+j,1);
            add(n*n+n*i+j,n*(i-1)+j,1);
        }
    for(int i=1;i<=n;i++)
    {
        add(n*n+i,T,1);
        add(n*n+(n-1)*n+i,T,1);
    }
    for(int i=2;i<n;i++)
    {
        add(n*n+n*(i-1)+1,T,1);
        add(n*n+n*i,T,1);
    }
    while(bfs())
        ans+=dinic(S,inf);
    if(ans>=m) cout<<"YES";
    else cout<<"NO";
    return 0;
}