题意：给出一个N*M的矩阵，0表示空地，1表示有一只羊，2表示有一只狼，你可以再图上方格的边缘添加单位长度为1的栅栏使得任意的动物都不能通过。问最少添加多少个单位长度为1的栅栏使得狼抓不到羊。
是我想的太多了，可能是因为我想少去建条边。其实这里件图建的还是很暴力的。对所有相邻的格子，都建一条cap=1的边，另外，所有有羊的格子，从源点S到羊所在的格子建一条cap=inf的边，对所有有狼的格子，都从有狼的格子到汇点T建一条cap=1的边。求出的最小割容量就是答案。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 41000 7 #define maxm 400000 8 using namespace std; 9 10 int v[maxm],next[maxm],w[maxm]; 11 int first[maxn],d[maxn],work[maxn],q[maxn]; 12 int n,m,maxflow,mincost,bg_cnt,e_cnt,t_cnt; 13 int e,S,T; 14 15 void init(){ 16 e = 0; 17 memset(first,-1,sizeof(first)); 18 } 19 20 void add_edge(int a,int b,int c){ 21 //printf("add:%d to %d,cap = %d ",a,b,c); 22 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 23 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 24 } 25 26 int bfs(){ 27 int rear = 0; 28 memset(d,-1,sizeof(d)); 29 d[S] = 0;q[rear++] = S; 30 for(int i = 0;i < rear;i++){ 31 for(int j = first[q[i]];j != -1;j = next[j]) 32 if(w[j] && d[v[j]] == -1){ 33 d[v[j]] = d[q[i]] + 1; 34 q[rear++] = v[j]; 35 if(v[j] == T) return 1; 36 } 37 } 38 return 0; 39 } 40 41 int dfs(int cur,int a){ 42 if(cur == T) return a; 43 for(int &i = work[cur];i != -1;i = next[i]){ 44 if(w[i] && d[v[i]] == d[cur] + 1) 45 if(int t = dfs(v[i],min(a,w[i]))){ 46 w[i] -= t;w[i^1] += t; 47 return t; 48 } 49 } 50 return 0; 51 } 52 53 int dinic(){ 54 int ans = 0; 55 while(bfs()){ 56 memcpy(work,first,sizeof(first)); 57 while(int t = dfs(S,INF)) ans += t; 58 } 59 return ans; 60 } 61 62 int main() 63 { 64 int n,m,kase = 0; 65 while(scanf("%d%d",&n,&m) == 2){ 66 S = 0,T = n*m+1; 67 init(); 68 for(int i = 1;i <= n;i++){ 69 for(int j = 1;j <= m;j++){ 70 int pos = (i-1)*m+j; 71 if(i > 1) add_edge(pos,pos-m,1); 72 if(i < n) add_edge(pos,pos+m,1); 73 if(j > 1) add_edge(pos,pos-1,1); 74 if(j < m) add_edge(pos,pos+1,1); 75 int tmp; 76 scanf("%d",&tmp); 77 if(tmp == 1) add_edge(S,pos,INF); 78 if(tmp == 2) add_edge(pos,T,INF); 79 } 80 } 81 int ans = dinic(); 82 printf("Case %d: %d ",++kase,ans); 83 } 84 return 0; 85 }