题目描述

“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。 通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。

输入

文件的第一行包含两个整数n和m。接下来n行每行m个整数，1表示该格子属于狼的领地，2表示属于羊的领地，0表示该格子不是任何一只动物的领地。

输出

文件中仅包含一个整数ans，代表篱笆的最短长度。

 

因为每块领地都是正方形格子，我们把相邻格子连起来，再沿着格子边缘画篱笆，可以发现：篱笆恰好把连的边割开了，这道题其实就是求最小割！把问题转换成求最大流就行了，将狼从源点连过来，将羊连向汇点。那么0怎么办？如果把它划分给狼或者羊，一定会有更优的解，那就直接把0放在狼和羊中间，这样就是S—>狼—>0—>羊—>T。然后直接跑最大流即可。

最后附上代码。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int next[1000001];int to[1000001];int val[1000001];int head[1000001];int tot=1;int q[1000001];int s[120][120];int n,m;int S,T;int ans;int d[1000001];const int INF=0x3f3f3f3f;void add(int x,int y,int v){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y; val[tot]=v; tot++; next[tot]=head[y]; head[y]=tot; to[tot]=x; val[tot]=0;} bool bfs(int S,int T){ int r=0; int l=0; memset(d,-1,sizeof(d)); q[r++]=S; d[S]=0; while(l
            
             =1&&(s[i-1][j]==2||s[i-1][j]==0)) { add(x,m*(i-2)+j,1); } if(j-1>=1&&(s[i][j-1]==2||s[i][j-1]==0)) { add(x,m*(i-1)+j-1,1); } if(i+1<=n&&(s[i+1][j]==2||s[i+1][j]==0)) { add(x,m*i+j,1); } if(j+1<=m&&(s[i][j+1]==2||s[i][j+1]==0)) { add(x,m*(i-1)+j+1,1); } } } } dinic(); printf("%d",ans); return 0;}