[ZJOI2009狼与羊的故事]网络流

题目描述

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

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

输出格式：

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

分析：
首先分析题目，建篱笆的本质就是使羊和狼之间没有通路（0可以为狼和羊两者的领地），而最小割是使源点和汇点之间没有通路。故可以借助网络流的最小割来完成。
表示因为数组开小了而WA，边数组要开到10倍。

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=110;
const int INF=1e9;
int a[maxn][maxn];
int n,m;
int s,t;
int to[maxn*maxn*10],Next[maxn*maxn*10],Begin[maxn*maxn],w[maxn*maxn*10],e;
int dis[maxn*maxn],gap[maxn*maxn],id[maxn][maxn];
int d[4][2]={0,1,0,-1,1,0,-1,0};
void add(int x,int y,int z){to[++e]=y;Next[e]=Begin[x];Begin[x]=e;w[e]=z;if(z!=0) add(y,x,0);
}
int isap(int x,int flow){if(x==t) return flow;int res=flow,v;for(int i=Begin[x];i;i=Next[i])if(w[i]>0 && dis[x]==dis[v=to[i]]+1){int Min=isap(v,min(res,w[i]));w[i]-=Min;w[i^1]+=Min;res-=Min;if(!res) return flow;}if(!--gap[dis[x]]) dis[s]=t;++gap[++dis[x]];return flow-res;
}
int main(){int cnt;e=1,cnt=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);id[i][j]=++cnt;}s=n*m+1;t=s+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i][j]==1) add(s,id[i][j],INF);else if(a[i][j]==2){add(id[i][j],t,INF);continue;}for(int k=0;k<4;k++){int x=i+d[k][0],y=j+d[k][1];if(x<1 || x>n || y<1 || y>m) continue;if(a[x][y]!=1) add(id[i][j],id[x][y],1);}}int maxflow=0;for(gap[0]=t;dis[s]s,INF);}printf("%d",maxflow);return 0;
}

^_^

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！