题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1412

思路：最大流求最小割，每个点向四周的点连容量至少为4的边，然后对于每个1的点，从源点向该点连容量1的边，对于每个2的点，从改点向汇点连容量为1的边，跑一次最大流即可。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

 

using namespace std;

 

#define MAXN 101

#define MAXV 10010

 

struct node {

    node *next,*pair;

    int t,f;

};

 

node *head[MAXV],*d[MAXV];

 

int gap[MAXV],h[MAXV];

int n,m;

int a[MAXN][MAXN],N[MAXN][MAXN];

int v=0;

int S,T;

 

void INSERT(int s,int t,int f){

    node *p=new(node);

    p->t=t;

    p->f=f;

    p->next=head[s];

    head[s]=p;

    p=new(node);

    p->t=s;

    p->f=0;

    p->next=head[t];

    head[t]=p;

    head[s]->pair=head[t];

    head[t]->pair=head[s];

}

 

int sap(int v,int flow){

    if (v==T){

        return flow;

    }

    int rec=0;

    for (node *p=d[v];p;p=p->next){

        if (p->f&&h[v]==h[p->t]+1){

            int ret=sap(p->t,min(flow-rec,p->f));

            p->f-=ret;

            p->pair->f+=ret;

            d[v]=p;

            if ((rec+=ret)==flow){

                return flow;

            }

        }

    }

    if (!(--gap[h[v]])){

        h[S]=T;

    }

    gap[++h[v]]++;

    d[v]=head[v];

    return rec;

}

 

int main(){

    memset(head,0,sizeof(head));

    memset(gap,0,sizeof(gap));

    memset(h,0,sizeof(h));

    scanf("%d%d",&n,&m);

    for (int i=0;i++<n;){

        for (int j=0;j++<m;){

            N[i][j]=++v;

            scanf("%d",&a[i][j]);

        }

    }

    S=++v;

    T=++v;

    for (int i=0;i++<n;){

        for (int j=0;j++<m;){

            if (i-1){

                INSERT(N[i][j],N[i-1][j],1);

            }

            if (j-1){

                INSERT(N[i][j],N[i][j-1],1);

            }

            if (i+1<=n){

                INSERT(N[i][j],N[i+1][j],1);

            }

            if (j+1<=m){

                INSERT(N[i][j],N[i][j+1],1);

            }

            switch (a[i][j]){

                case 1:

                    INSERT(S,N[i][j],0x7fffffff);

                    break;

                case 2:

                    INSERT(N[i][j],T,0x7fffffff);

                    break;

            }  

        }

    }

    gap[0]=T;

    for (int i=0;i++<T;){

        d[i]=head[i];

    }

    int mincut=0;

    while (h[S]<T){

        mincut+=sap(S,0x7fffffff);

    }

    printf("%d\n",mincut);

    return 0;

}