P2598 [ZJOI2009]狼和羊的故事题解

wxwoo

2019-03-13

题解 / 洛谷

原题目链接

将狼和羊分成两个部分：~~明显的~~最小割

根据最大流最小割定理，最大流=最小割，所以这题可以使用最大流算法求解

我们将每个格子看成一个点，然后如下建边：

源点向狼的领地连流量为$inf$的边

羊的领地向汇点连流量为$inf$的边

每个格子向上下左右四个格子连流量为$1$的边

接下来我们思考这样建边的正确性

在最小割模型中，连一条流量为$inf$的边意为连一条不可割边（这套路很常见的）

那么这个图中的可割边就只有两个格子之间的边了

接下来我们考虑那些为$0$的格子

由于最小割的性质，狼和羊一定会被分成两部分，和为$0$的格子无关

代码如下

#include<cstdio>
#include<cstring>
using namespace std;
const int inf=1e9;
const int N=3e5+1;
struct edge
{
    int from,to,next,cap,flow;
}e[N];
int cnt,n,m,sour,sink,head[N],ans,q[N],l[N],p[N];
const int move[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
inline int min(int i,int j)
{
    return i<j?i:j;
}
inline void add(int u,int v,int l)
{
    e[++cnt]=(edge){u,v,head[u],l,0};
    head[u]=cnt;
    e[++cnt]=(edge){v,u,head[v],0,0};
    head[v]=cnt;
}
inline bool find()
{
    memset(l,0,sizeof(l));
    int h=1,t=1;
    q[1]=sour;
    l[sour]=1;
    while(h<=t)
    {
        int x=q[h++];
        for(int i=head[x];i;i=e[i].next)
            if(!l[e[i].to]&&e[i].cap>e[i].flow)
            {
                q[++t]=e[i].to;
                l[e[i].to]=l[x]+1;
                if(e[i].to==sink)
                    return true;
            }
    }
    return false;
}
int dfs(int x,int now)
{
    if(x==sink||!now)
        return now;
    int t=now,detla;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].cap>e[i].flow&&l[e[i].to]==l[x]+1)
        {
            detla=dfs(e[i].to,min(t,e[i].cap-e[i].flow));
            if(!detla)
                l[e[i].to]=0;
            e[i].flow+=detla;
            e[((i-1)^1)+1].flow-=detla;
            t-=detla;
            if(t==0)
                break;
        }
    }
    return now-t;
}
inline void dinic()
{
    while(find())
        ans+=dfs(sour,inf);
}
inline void read(int &x)
{
    char ch;
    int f=1;
    x=0;
    do
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }while(!('0'<=ch&&ch<='9'));
    do
    {
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }while('0'<=ch&&ch<='9');
    x*=f;
}
inline int get(int x,int y)
{
    return (x-1)*m+y;
}
int main()
{
    read(n);
    read(m);
    sour=0;
    sink=n*m+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int t;
            read(t);
            if(t==2)
            	add(get(i,j),sink,inf);
            else if(t==1)
            	add(sour,get(i,j),inf);
            for(int k=0;k<4;k++)
            {
            	int x=i+move[k][0],y=j+move[k][1];
            	if(x<1||x>n||y<1||y>m)
            		continue;
            	add(get(i,j),get(x,y),1);
            }
        }
    }
    dinic();
    printf("%d",ans);
    return 0;
}