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
Solution
将源点向所有羊连边，所有羊向不是任何一只动物的领地和狼连边，不是任何一只动物的领地向狼连边，狼向汇点连边，求最小割即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<iostream> #include<cstdio> using namespace std; const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; int n,m,tot,cnt,a[105][105],p[105][105],Next[80100],head[10010],tree[80100],val[80100]; int h[10010],x[10010],cur[10010]; void Add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void add(int x,int y,int z) { Add(x,y,z);Add(y,x,0); } bool bfs() { int t=0,w=1; for (int i=1;i<=cnt+2;i++) h[i]=-1; x[1]=cnt+1;h[cnt+1]=0; while (t!=w) { int u=x[++t]; for (int i=head[u];i;i=Next[i]) if (val[i]&&h[tree[i]]==-1) { x[++w]=tree[i]; h[tree[i]]=h[u]+1; } } return h[cnt+2]!=-1; } int dfs(int u,int low) { if (u==cnt+2) return low; int used=0; for (int i=cur[u];i;i=Next[i]) { int v=tree[i]; if (h[v]==h[u]+1&&val[i]) { int w=dfs(v,min(val[i],low-used)); val[i]-=w;val[i^1]+=w; used+=w; cur[u]=i; if (used==low) return low; } } if (used==0) h[u]=-1; return used; } int dinic() { int ans=0; while (bfs()) { for (int i=1;i<=cnt+2;i++) cur[i]=head[i]; ans+=dfs(cnt+1,1<<29); } return ans; } int main() { scanf("%d%d",&n,&m); tot=1;cnt=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]),p[i][j]=++cnt; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (a[i][j]==1) add(cnt+1,p[i][j],1<<28); if (a[i][j]==2) add(p[i][j],cnt+2,1<<28); if (a[i][j]!=2) for (int k=0;k<=3;k++) if (p[i+dx[k]][j+dy[k]]) add(p[i][j],p[i+dx[k]][j+dy[k]],1); } printf("%d\n",dinic()); return 0; } |
%%%
orz