每个栅栏其实就是一条边，修一些栅栏，使得狼不能抓到羊，其实就是求一个割，使得羊全在S中，狼全在T中。
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <queue> 5 #define maxn 40010 6 #define oo 0x3f3f3f3f 7 #define clr(arr,n) memset(&arr,0,sizeof(arr[0])*(n+1)) 8 using namespace std; 9 10 struct Edge { 11 int u, v, f; 12 Edge( int u, int v, int f ):u(u),v(v),f(f){} 13 }; 14 struct Dinic { 15 int n, src, dst; 16 vector<Edge> edge; 17 vector<int> g[maxn]; 18 int dep[maxn], cur[maxn]; 19 20 void init( int n, int src, int dst ) { 21 this->n = n; 22 this->src = src; 23 this->dst = dst; 24 for( int u=1; u<=n; u++ ) 25 g[u].clear(); 26 edge.clear(); 27 } 28 void add_edge( int u, int v, int f ) { 29 g[u].push_back( edge.size() ); 30 edge.push_back( Edge(u,v,f) ); 31 g[v].push_back( edge.size() ); 32 edge.push_back( Edge(v,u,0) ); 33 } 34 bool bfs() { 35 queue<int> qu; 36 clr( dep, n ); 37 qu.push(src); 38 dep[src] = 1; 39 while( !qu.empty() ) { 40 int u=qu.front(); 41 qu.pop(); 42 for( int t=0; t<g[u].size(); t++ ) { 43 Edge &e=edge[g[u][t]]; 44 if( e.f && !dep[e.v] ) { 45 dep[e.v] = dep[e.u]+1; 46 qu.push( e.v ); 47 } 48 } 49 } 50 return dep[dst]; 51 } 52 int dfs( int u, int a ) { 53 if( u==dst || a==0 ) return a; 54 int remain=a, past=0, na; 55 for( int &t=cur[u]; t<g[u].size(); t++ ) { 56 Edge &e = edge[g[u][t]]; 57 Edge &ve = edge[g[u][t]^1]; 58 if( e.f && dep[e.v]==dep[e.u]+1 && (na=dfs(e.v,min(e.f,remain))) ) { 59 remain -= na; 60 past += na; 61 e.f -= na; 62 ve.f += na; 63 if( remain==0 ) break; 64 } 65 } 66 return past; 67 } 68 int maxflow() { 69 int flow = 0; 70 while(bfs()) { 71 clr( cur, n ); 72 flow += dfs(src,oo); 73 } 74 return flow; 75 } 76 }; 77 78 int n, m; 79 int idx[210][210], id_clock; 80 int map[210][210]; 81 int dx[2] = { +1, 0 }; 82 int dy[2] = { 0, +1 }; 83 Dinic D; 84 85 int main() { 86 for( int cas=1; ; cas++ ) { 87 if( scanf( "%d%d", &n, &m )!=2 ) return 0; 88 id_clock = 0; 89 for( int i=1; i<=n; i++ ) 90 for( int j=1; j<=m; j++ ) { 91 scanf( "%d", &map[i][j] ); 92 idx[i][j] = ++id_clock; 93 } 94 D.init( id_clock+2, id_clock+1, id_clock+2 ); 95 for( int i=1; i<=n; i++ ) 96 for( int j=1; j<=m; j++ ) 97 for( int d=0; d<2; d++ ) { 98 int ni = i+dx[d]; 99 int nj = j+dy[d]; 100 if( 1<=ni&&ni<=n && 1<=nj&&nj<=m ) { 101 int u = idx[i][j]; 102 int v = idx[ni][nj]; 103 D.add_edge( u, v, 1 ); 104 D.add_edge( v, u, 1 ); 105 } 106 } 107 for( int i=1; i<=n; i++ ) 108 for( int j=1; j<=m; j++ ) { 109 if( map[i][j]==1 ) 110 D.add_edge( D.src, idx[i][j], oo ); 111 if( map[i][j]==2 ) 112 D.add_edge( idx[i][j], D.dst, oo ); 113 } 114 printf( "Case %d: %d ", cas, D.maxflow() ); 115 } 116 }