[bzoj1412][ZJOI2009]狼和羊的故事

bzoj100题啦  纪念一下。

----------------------------------------------------------------------------------------------------------------------------------------------

题意：给定一个n*m的图，每一个点可以是狼，用2表示，或者是1-羊，或者是0，表示这里没有动物。你要修尽量少的围墙，使得狼和羊都被隔开。

狼和羊的故事，题解：很容易想到最小割。我们从S向每一头羊连INF的边，狼向T连INF的边，然后羊或者空点都向四周羊以外的点连边，跑最小割。

#include<iostream>
#include<cstdio>
#include<cstring>
#define S 0
#define T 10001
#define INF 2000000000
using namespace std;
inline int read()
{int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}int d[T+5],c[T+5],head[T+5],n,m,q[T+5],top,cnt=1;
int st[105][105];
const int dis[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct edge{int to,next,w;}e[T*100];void ins(int f,int t,int w)
{e[++cnt]=(edge){t,head[f],w};head[f]=cnt;e[++cnt]=(edge){f,head[t],0};head[t]=cnt;//cout<<"ins"<<f<<" "<<t<<" "<<w<<endl; 
}int dfs(int x,int f)
{if(x==T)return f;int used=0;for(int&i=c[x];i;i=e[i].next)if(e[i].w&&d[e[i].to]==d[x]+1){int w=dfs(e[i].to,min(f-used,e[i].w));used+=w;e[i].w-=w;e[i^1].w+=w;if(used==f)return f;}return d[x]=0,used;
}bool bfs()
{memset(d,0,sizeof(d));int i,j;for(d[q[top=i=0]=S]=1;i<=top;i++)for(int j=c[q[i]]=head[q[i]];j;j=e[j].next)if(e[j].w&&!d[e[j].to])d[q[++top]=e[j].to]=d[q[i]]+1;return d[T];
}int main()
{n=read();m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)st[i][j]=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(st[i][j]==1) ins(S,(i-1)*m+j,INF);if(st[i][j]==2) ins((i-1)*m+j,T,INF);if(st[i][j]==2) continue;for(int k=0;k<4;k++){int xx=i+dis[k][0],yy=j+dis[k][1];if(xx<1||yy<1||xx>n||yy>m) continue;if(st[xx][yy]!=1)ins((i-1)*m+j,(xx-1)*m+yy,1);    }}int ans=0;while(bfs()) ans+=dfs(S,INF);cout<<ans;return 0;
}