Description
“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。 通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。
Input
文件的第一行包含两个整数n和m。接下来n行每行m个整数，1表示该格子属于狼的领地，2表示属于羊的领地，0表示该格子不是任何一只动物的领地。
Output
文件中仅包含一个整数ans，代表篱笆的最短长度。
Sample Input
2 2
2 2
1 1
2 2
1 1
Sample Output
2
数据范围
10%的数据 n，m≤3
30%的数据 n，m≤20
100%的数据 n，m≤100
又是网络流，有没建出模型来……
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int inf=,N=;
int fx[]={,,,-},fy[]={,-,,};
struct ee{int to,next,f;}e[];
int head[N*N],q[N**N],dis[N*N],a[N][N];
int S,T,n,m,cnt=,ans,w; void ins(int u,int v,int f){
e[++cnt].to=v;e[cnt].f=f;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].f=;e[cnt].next=head[v];head[v]=cnt;
} bool bfs(){
for (int i=;i<=T;i++) dis[i]=inf;
int h=,t=,now;
q[]=S;dis[S]=;
while(h!=t){
now=q[++h];
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (e[i].f&&dis[now]+<dis[v]){
dis[v]=dis[now]+;
if (v==T)return ;
q[++t]=v;
}
}
}
if (dis[T]==inf) return ; return ;
} int dinic(int now,int f){
if (now==T) return f;
int rest=f;
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (e[i].f&&dis[v]==dis[now]+&&rest){
int t=dinic(v,min(rest,e[i].f));
if (!t) dis[v]=;
e[i].f-=t;
e[i^].f+=t;
rest-=t;
//if(t) printf("%d %d %d\n",now,v,e[i].f);
}
}
return f-rest;
}
int main(){
scanf("%d%d",&n,&m);
S=,T=n*m+;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=;i<=n;i++) for(int j=;j<=m;j++)
if(a[i][j]==) ins(S,(i-)*m+j,inf);
for(int i=;i<=n;i++) for(int j=;j<=m;j++)
if(a[i][j]==) ins((i-)*m+j,T,inf);
for(int i=;i<=n;i++) for(int j=;j<=m;j++){
if(a[i][j]==) {
for(int ii=;ii<;ii++) {
int nx=i+fx[ii],ny=j+fy[ii];
if(nx>n||nx<||ny>m||ny<||a[nx][ny]==) continue;
ins((i-)*m+j,(nx-)*m+ny,);
}
}
else if(a[i][j]==){
for(int ii=;ii<;ii++) {
int nx=i+fx[ii],ny=j+fy[ii];
if(nx>n||nx<||ny>m||ny<||a[nx][ny]==) continue;
ins((i-)*m+j,(nx-)*m+ny,);
}
}
}
while(bfs())
ans+=dinic(S,inf);
printf("%d",ans);
}