BZOJ-3144: [Hnoi2013]切糕（最小割）

挺神奇的一个最小割模型，对于限制2自己动手画图YY一下就可以啦~。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 50
#define inf 0x7fffffff
#define MAXV 100010
 
struct network {
      
    struct edge {
        edge *next , *pair ;
        int t , f ;
    } *head[ MAXV ] ;
      
    void Add( int s , int t , int f ) {
        edge *p = new( edge ) ;
        p -> t = t , p -> f = f , p -> next = head[ s ] ;
        head[ s ] = p ;
    }
      
    void AddEdge( int s , int t , int f ) {
        Add( s , t , f ) ,Add( t , s , 0 ) ;
        head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;
    }
      
    int S , T ;
      
    network(  ) {
        memset( head , 0 , sizeof( head ) ) ;
    }
      
    int h[ MAXV ] , gap[ MAXV ] ;
    edge *d[ MAXV ] ;
      
    int sap( int v , int flow ) {
        if ( v == T ) return flow ;
        int rec = 0 ;
        for ( edge *p = d[ v ] ; p ; p = p -> next ) if ( p -> f && h[ v ] == h[ p -> t ] + 1 ) {
            int ret =sap( p -> t ,min( flow - rec , p -> f ) ) ;
            p -> f -= ret , p -> pair -> f += ret , d[ v ] = p ;
            if ( ( rec += ret ) == flow ) return flow ;
        }
        if ( ! ( -- gap[ h[ v ] ] ) ) h[ S ] = T ;
        gap[ ++ h[ v ] ] ++ , d[ v ] = head[ v ] ;
        return rec ;
    }
      
    int maxflow(  ) {
        int flow = 0 ; 
        memset( h , 0 , sizeof( h ) ) ;
        memset( gap , 0 , sizeof( gap ) ) ;
        for ( int i = 0 ; i ++ < T ; ) d[ i ] = head[ i ] ;
        gap[ S ] = T ;
        while ( h[ S ] < T ) flow +=sap( S , inf ) ;
        return flow ;
    }
      
} net ;
 
int n , m , h , D , node[ MAXN ][ MAXN ][ MAXN ] , V = 0 ;
const int dir[ 4 ][ 2 ] = { { -1 , 0 } , { 1 , 0 } , { 0 , 1 } , { 0 , -1 } } ;
 
int main(  ) {
    scanf( "%d%d%d%d" , &n , &m , &h , &D ) ;
    for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) {
        for ( int k = 0 ; k ++ < h + 1 ; ) node[ i ][ j ][ k ] = ++ V ;
    }
    net.S = ++ V ; net.T = ++ V ;
    for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) {
        net.AddEdge( net.S , node[ i ][ j ][ 1 ] , inf ) ;
        net.AddEdge( node[ i ][ j ][ h + 1 ] , net.T , inf ) ;
    }
    for ( int k = 0 ; k ++ < h ; ) {
        for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) {
            int x ;scanf( "%d" , &x ) ;
            net.AddEdge( node[ i ][ j ][ k ] , node[ i ][ j ][ k + 1 ] , x ) ;
        }
    }
    for ( int k = 0 ; k ++ < h - D + 1 ; ) {
        for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) {
            for ( int w = 0 ; w < 4 ; w ++ ) {
                int x = i + dir[ w ][ 0 ] , y = j + dir[ w ][ 1 ] ;
                if ( x <=0 || y <=0 || x > n || y > m ) continue ;
                net.AddEdge( node[ i ][ j ][ k + D ] , node[ x ][ y ][ k ] , inf ) ;
            }
        }
    }
    printf( "%d\n" , net.maxflow(  ) ) ;
    return 0 ;
}