題目:http://www.lydsy.com/JudgeOnline/problem.php?id=3144
挺神奇的一個(gè)最小割模型,對(duì)于限制2自己動(dòng)手畫圖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 ;
}