传送门:【HDU】3035 War
题目分析:赤裸裸的对偶图全局最小割,最短路套上就好了。
debug了半天结果是define出了问题。。。唉。。果然是有副作用的。。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define REV( i , n ) for ( int i = n - 1 ; i >= 0 ; -- i ) #define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define REPF( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define REPV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof a ) #define CPY( a , x ) memcpy ( a , x , sizeof a ) #define U( i , j ) ( ( ( ( i ) * m + ( j ) ) << 2 ) + 0 ) #define D( i , j ) ( ( ( ( i ) * m + ( j ) ) << 2 ) + 1 ) #define L( i , j ) ( ( ( ( i ) * m + ( j ) ) << 2 ) + 2 ) #define R( i , j ) ( ( ( ( i ) * m + ( j ) ) << 2 ) + 3 ) const int MAXN = 1000000 + 5 ; const int MAXQ = 1000000 + 5 ; const int MAXE = 3000000 + 5 ; const int INF = 0x7f7f7f7f ; struct Edge { int v , c , n ; Edge () {} Edge ( int v , int c , int n ) : v ( v ) , c ( c ) , n ( n ) {} } ; struct Graph { Edge E[MAXE] ; int H[MAXN] , cntE ; int d[MAXN] ; int Q[MAXQ] , head , tail ; bool inq[MAXN] ; int n , m ; int s , t ; void init () { cntE = 0 ; CLR ( H , -1 ) ; } void addedge ( int u , int v , int c ) { E[cntE] = Edge ( v , c , H[u] ) ; H[u] = cntE ++ ; E[cntE] = Edge ( u , c , H[v] ) ; H[v] = cntE ++ ; } void spfa () { CLR ( inq , false ) ; CLR ( d , INF ) ; head = tail = 0 ; d[s] = 0 ; Q[tail ++] = s ; while ( head != tail ) { int u = Q[head ++] ; if ( head == MAXQ ) head = 0 ; inq[u] = false ; for ( int i = H[u] ; ~i ; i = E[i].n ) { int v = E[i].v ; if ( d[v] > d[u] + E[i].c ) { d[v] = d[u] + E[i].c ; if ( !inq[v] ) { inq[v] = true ; if ( d[v] < d[Q[head]] ) { if ( head == 0 ) Q[head = MAXQ - 1] = v ; else Q[-- head] = v ; } else { Q[tail ++] = v ; if ( tail == MAXQ ) tail = 0 ; } } } } } } void read ( int &x ) { x = 0 ; char c = ' ' ; while ( c < '0' || c > '9' ) c = getchar () ; while ( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar () ; } } void input () { int x ; s = n * m * 4 ; t = s + 1 ; FOR ( i , 0 , n ) REP ( j , m ) { read ( x ) ; if ( i == 0 ) addedge ( U ( i , j ) , t , x ) ; else if ( i < n ) addedge ( U ( i , j ) , D ( i - 1 , j ) , x ) ; else addedge ( s , D ( i - 1 , j ) , x ) ; } REP ( i , n ) FOR ( j , 0 , m ) { read ( x ) ; if ( j == 0 ) addedge ( s , L ( i , j ) , x ) ; else if ( j < m ) addedge ( R ( i , j - 1 ) , L ( i , j ) , x ) ; else addedge ( R ( i , j - 1 ) , t , x ) ; } REP ( i , n << 1 ) REP ( j , m << 1 ) { read ( x ) ; int ii = i >> 1 , jj = j >> 1 ; if ( ( i & 1 ) == 0 && ( j & 1 ) == 0 ) addedge ( L ( ii , jj ) , U ( ii , jj ) , x ) ; else if ( ( i & 1 ) == 0 && ( j & 1 ) == 1 ) addedge ( U ( ii , jj ) , R ( ii , jj ) , x ) ; else if ( ( i & 1 ) == 1 && ( j & 1 ) == 0 ) addedge ( L ( ii , jj ) , D ( ii , jj ) , x ) ; else if ( ( i & 1 ) == 1 && ( j & 1 ) == 1 ) addedge ( D ( ii , jj ) , R ( ii , jj ) , x ) ; } } void solve () { init () ; input () ; spfa () ; printf ( "%d\n" , d[t] ) ; } } x ; int main () { while ( ~scanf ( "%d%d" , &x.n , &x.m ) ) x.solve () ; return 0 ; }