P2598 [ZJOI2009]狼和羊的故事

网络最大流。

前言：上课滑水，晚上做题一脸蒙，感谢隔壁的帮助（）

修建栏杆相当于是割断了狼和羊之间的联系方式，即割掉了一条边。在网格图中，建边的方式为由现在所在的格子向周围四个方向的格子连一条边。（理论上建立反向边比较赘余，但是因为在跑 Dinic 过程中涉及$i$（本条边）和$i \land 1$（反向边）的使用，所以还是建上吧！)因此，在网络流中，要求割最少的边，使得网络不流通，这不就是网络流最小割问题嘛？

最小割$=$最大流

所以在建图以后直接跑 Dinic 就好了。

当当当当然，只知道建立网格图的网络流肯定是不够的，狼和羊之间的关系应该怎么处理呢？

最小割问题指的是，割去一些边之后，源点到汇点不再流通。

这里要求一定要把狼和羊严格隔开，距离无法隔开他们，也就是说即使他们隔着很多个$0$的格子，也是可以互相到达的！这就不满足题目条件了。

应该就很明显了，这道题就是裸的网络流最小割问题欸。

总结：

• 二维图中用一个数字存储一个坐标：$(i-1)*m+j$
• 因为是二，维，图，所以建图的数组要开$maxn*maxn$！
• $cnt$的初始值应该赋值为$1$，因为你在跑 Dinic 的时候，以下这一段容易出事：

ll fj=dfs(to,min(e[i].dis,limit));
e[i].dis-=fj;
e[i^1].dis+=fj;

• 加边一定要加反向边啊啊啊！

#include <bits/stdc++.h>
#define ll long long
#define maxn 42100
#define INF 1000000000
using namespace std;
ll n,m;
ll q[maxn],l,r,d[maxn];
ll a[110][110];
ll ans;
ll s,t;
ll cnt=1,hd[maxn];
ll fx[5][3]={{0,1},{0,-1},{1,0},{-1,0}};
struct Node{
    ll nx,to,dis;
}e[maxn*4];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline ll sm(ll u,ll v){
    return (u-1)*m+v;
}

inline void add(ll u,ll v,ll w){
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].nx=hd[u];
    hd[u]=cnt;
}

inline ll bfs(){
    memset(d,0,sizeof(d));
    l=r=1;
    q[l]=s;
    d[s]=1;
    while(l<=r){
        ll u=q[l++];
        for(register int i=hd[u];i;i=e[i].nx){
            ll to=e[i].to;
            if(!d[to]&&e[i].dis){
                d[to]=d[u]+1;
                q[++r]=to;
            }
        }
    }
    return d[t];
}

inline ll dfs(ll u,ll limit){
    if(u==t)
        return limit;
    ll flow=0;
    for(register int i=hd[u];i&&limit;i=e[i].nx){
        ll to=e[i].to;
        if(e[i].dis&&d[to]==d[u]+1){
            ll fj=dfs(to,min(e[i].dis,limit));
            e[i].dis-=fj;
            e[i^1].dis+=fj;
            limit-=fj;
            flow+=fj;
        }
    }
    if(!flow)   d[u]=0;
    return flow;
}

int main(){
    n=read();m=read();
    s=n*m*2+1,t=n*m*2+2;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            a[i][j]=read();
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j){
            if(a[i][j]==2){
                add(s,sm(i,j),INF);
                add(sm(i,j),s,0);   

            }
            else if(a[i][j]==1){
                add(sm(i,j),t,INF);
                add(t,sm(i,j),0);
            }
        }
    }        
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            for(register int k=0;k<=3;++k){
                ll dx=i+fx[k][0];
                ll dy=j+fx[k][1];
                if(dx>=1&&dx<=n&&dy>=1&&dy<=m)
                    add(sm(i,j),sm(dx,dy),1),
                    add(sm(dx,dy),sm(i,j),0);
            }       
    while(bfs())
        ans+=dfs(s,INF);
    printf("%lld\n",ans);
    return 0;
}