HDU3046_Pleasant sheep and big big wolf

给一个n*m的数字阵，1表示羊的位置，2表示狼的位置，0表示没有东西，可以通过。在每个格子的4边都可以建立围栏，有围栏的话狼是不能通过的。

现在求最少建立多少围栏能够保证狼无法接触到羊。

题目的模型很简单，直接建立一个超级源点和超级汇点，狼连接远点流量无穷大，羊连接汇点流量无穷大，每个格子和四周的四个格子建立一条流量为1的边，要把狼羊分离就是求最小割了，最大流等于最小割，圆满解决问题。

召唤代码君：

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100100
#define inf 99999999
using namespace std;

int to[maxn],c[maxn],first[maxn],next[maxn],N;
int d[maxn];
int s,t,n,m,tmp,ans,cas=0;
int Q[maxn],bot,top,tag[maxn],can[maxn],TAG=423;

void _init()
{
    ans=s=0,t=n*m+1,N=-1;
    for (int i=s; i<=t; i++) first[i]=-1;
}

void edge(int U,int V,int W)
{
    N++;
    to[N]=V,c[N]=W;
    next[N]=first[U],first[U]=N;
}

void _input()
{
    int cur=0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            scanf("%d",&tmp);
            cur++;
            if (i<n) edge(cur,cur+m,1),edge(cur+m,cur,1);
            if (j<m) edge(cur,cur+1,1),edge(cur+1,cur,1);
            if (tmp==2) edge(s,cur,inf),edge(cur,s,inf);
                else if (tmp==1) edge(cur,t,inf),edge(t,cur,inf);
        }

}

bool bfs()
{
    TAG++;
    Q[bot=top=1]=t,d[t]=0,tag[t]=TAG;
    while (bot<=top)
    {
        int cur=Q[bot++];
        for (int i=first[cur]; i!=-1; i=next[i])
        {
            if (c[i^1]<=0 || tag[to[i]]==TAG) continue;
            tag[to[i]]=TAG,d[to[i]]=d[cur]+1,Q[++top]=to[i];
            if (to[i]==s) return true;
        }
    }
    return false;
}

int dfs(int cur,int num)
{
    if (cur==t) return num;
    int tmp=num,k;
    for (int i=first[cur]; i!=-1; i=next[i])
    {
        if (d[cur]!=d[to[i]]+1 || c[i]<=0 || tag[to[i]]!=TAG || can[to[i]]==TAG) continue;
        k=dfs(to[i],min(num,c[i]));
        if (k) c[i]-=k,c[i^1]+=k,num-=k;
        if (num==0) break;
    }
    if (num) can[cur]=TAG;
    return tmp-num;
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        _init();
        _input();
        while (bfs()) ans+=dfs(s,inf);
        printf("Case %d:
%d
",++cas,ans);
    }
    return 0;
}