hdu 3046 最小割

每个栅栏其实就是一条边，修一些栅栏，使得狼不能抓到羊，其实就是求一个割，使得羊全在S中，狼全在T中。

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <queue>

 #define maxn 40010

 #define oo 0x3f3f3f3f

 #define clr(arr,n) memset(&arr,0,sizeof(arr[0])*(n+1))

 using namespace std;

 struct Edge {

     int u, v, f;

     Edge( int u, int v, int f ):u(u),v(v),f(f){}

 };

 struct Dinic {

     int n, src, dst;

     vector<Edge> edge;

     vector<int> g[maxn];

     int dep[maxn], cur[maxn];

     void init( int n, int src, int dst ) {

         this->n = n;

         this->src = src;

         this->dst = dst;

         for( int u=; u<=n; u++ )

             g[u].clear();

         edge.clear();

     }

     void add_edge( int u, int v, int f ) {

         g[u].push_back( edge.size() );

         edge.push_back( Edge(u,v,f) );

         g[v].push_back( edge.size() );

         edge.push_back( Edge(v,u,) );

     }

     bool bfs() {

         queue<int> qu;

         clr( dep, n );

         qu.push(src);

         dep[src] = ;

         while( !qu.empty() ) {

             int u=qu.front();

             qu.pop();

             for( int t=; t<g[u].size(); t++ ) {

                 Edge &e=edge[g[u][t]];

                 if( e.f && !dep[e.v] ) {

                     dep[e.v] = dep[e.u]+;

                     qu.push( e.v );

                 }

             }

         }

         return dep[dst];

     }

     int dfs( int u, int a ) {

         if( u==dst || a== ) return a;

         int remain=a, past=, na;

         for( int &t=cur[u]; t<g[u].size(); t++ ) {

             Edge &e = edge[g[u][t]];

             Edge &ve = edge[g[u][t]^];

             if( e.f && dep[e.v]==dep[e.u]+ && (na=dfs(e.v,min(e.f,remain))) ) {

                 remain -= na;

                 past += na;

                 e.f -= na;

                 ve.f += na;

                 if( remain== ) break;

             }

         }

         return past;

     }

     int maxflow() {

         int flow = ;

         while(bfs()) {

             clr( cur, n );

             flow += dfs(src,oo);

         }

         return flow;

     }

 };

 int n, m;

 int idx[][], id_clock;

 int map[][];

 int dx[] = { +,  };

 int dy[] = { , + };

 Dinic D;

 int main() {

     for( int cas=; ; cas++ ) {

         if( scanf( "%d%d", &n, &m )!= ) return ;

         id_clock = ;

         for( int i=; i<=n; i++ )

             for( int j=; j<=m; j++ ) {

                 scanf( "%d", &map[i][j] );

                 idx[i][j] = ++id_clock;

             }

         D.init( id_clock+, id_clock+, id_clock+ );

         for( int i=; i<=n; i++ )

             for( int j=; j<=m; j++ )

                 for( int d=; d<; d++ ) {

                     int ni = i+dx[d];

                     int nj = j+dy[d];

                     if( <=ni&&ni<=n && <=nj&&nj<=m ) {

                         int u = idx[i][j];

                         int v = idx[ni][nj];

                         D.add_edge( u, v,  );

                         D.add_edge( v, u,  );

                     }

                 }

         for( int i=; i<=n; i++ )

             for( int j=; j<=m; j++ ) {

                 if( map[i][j]== )

                     D.add_edge( D.src, idx[i][j], oo );

                 if( map[i][j]== )

                     D.add_edge( idx[i][j], D.dst, oo );

             }

         printf( "Case %d:\n%d\n", cas, D.maxflow() );

     }

 }