Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
zkw流超时 , why ? 求大牛出手相助#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <map> #include <set> typedef long long LL ; typedef double DB ; const int max_int = ( 2147483647 ) , oo = ( 1000000000 ) ; #define ms memset #define mc memcpy #define gc getchar #define sz sizeof #define il inline #define Rep( k , x , y ) for ( k = x ; k <= y ; k ++ ) #define Repn( k , x , y ) for ( k = x ; k >= y ; k -- ) #define mk make_pair #define fi first #define se second #define puf push_front #define pub push_back #define pof pop_front #define pob pop_back #define sqr( x ) ( ( x ) * ( x ) ) using namespace std ; const int maxn = ( 50 ) , maxm = sqr( 300 ) , max_size = ( 2 * 300 + 2 + 10 ) ; #define ST ( 0 ) #define ED ( N ) #define from( x , y ) ( ( x - 1 ) * k + y ) #define to( x , y ) ( m * k + ( x - 1 ) * k + y ) struct edge_node { int y , val , cost , next ; #define e_y( k ) edge[ k ].y #define e_val( k ) edge[ k ].val #define e_cost( k ) edge[ k ].cost #define e_next( k ) edge[ k ].next } edge[ maxm ] ; int len , first[ max_size ] , n , m , k , d[ max_size ] , sum_st , ans , N , data[ maxn ][ maxn ] ; bool visit[ max_size ] ; deque < int > Q ; il void ins( int x , int y , int val , int cost ) { len ++ , e_y( len ) = y , e_val( len ) = val , e_cost( len ) = cost ; e_next( len ) = first[ x ] , first[ x ] = len ; return ; } il void insert( int x , int y , int val , int cost ) { ins( x , y , val , cost ) , ins( y , x , 0 , - cost ) ; return ; } il bool spfa() { int k , x ; ms( d , 63 , sz( int ) * ( N + 2 ) ) , Q.clear() ; for ( Q.pub( ED ) , d[ ED ] = 0 ; Q.size() ; ) { x = Q.front() , Q.pof() ; for ( k = first[ x ] ; k != ( - 1 ) ; k = e_next( k ) ) if ( e_val( k ^ 1 ) && ( d[ x ] - e_cost( k ) ) < d[ e_y( k ) ] ) ( ( d[ e_y( k ) ] = ( d[ x ] - e_cost( k ) ) ) < d[ Q.size() ? Q.front() : ST ] ) ? Q.puf( e_y( k ) ) : Q.pub( e_y( k ) ) ; } Rep ( x , ST , ED ) for ( k = first[ x ] ; k != ( - 1 ) ; k = e_next( k ) ) e_cost( k ) += ( d[ e_y( k ) ] - d[ x ] ) ; sum_st += d[ ST ] ; return ( d[ ST ] < d[ ED + 1 ] ) ; } il int aug( int w , int last ) { if ( w == ED ) return ans += last * sum_st , last ; int now = last , val , k ; for ( k = first[ w ] , visit[ w ] = 1 ; k != ( - 1 ) ; k = e_next( k ) ) if ( !e_cost( k ) && e_val( k ) && !visit[ e_y( k ) ] ) { val = aug( e_y( k ) , ( now > e_val( k ) ) ? ( e_val( k ) ) : ( now ) ) ; e_val( k ) -= val , e_val( k ^ 1 ) += val , now -= val ; if ( !now ) return last - now ; } return last - now ; } int main() { freopen( "input.txt" , "r" , stdin ) , freopen( "output.txt" , "w" , stdout ) ; int i , j , x , y , sum_up ; while ( scanf( "%d%d%d" , &n , &m , &k ) != EOF && ( n || m || k ) ) { if ( !n && !m && !k ) break ; len = - 1 , ms( first , 255 , sz( int ) * ( ( N = ( n * k + m * k + 1 ) ) + 10 ) ) , sum_up = ans = sum_st = 0 ; Rep ( i , 1 , n ) Rep ( j , 1 , k ) scanf( "%d" , &x ) , sum_up += x , insert( to( i , j ) , ED , x , 0 ) ; Rep ( i , 1 , m ) Rep ( j , 1 , k ) scanf( "%d" , &x ) , insert( ST , from( i , j ) , x , 0 ) ; Rep ( x , 1 , k ) Rep ( i , 1 , n ) Rep ( j , 1 , m ) scanf( "%d" , &y ) , insert( from( j , x ) , to( i , x ) , oo , y ) ; y = 0 ; while ( spfa() ) for ( ms( visit , 0 , sz( int ) * ( N + 10 ) ) ; x = aug( ST , max_int ) ; y += x , ms( visit , 0 , sz( int ) * ( N + 10 ) ) ) ; ( y < sum_up ) ? printf( "-1\n" ) : printf( "%d\n" , ans ) ; } return 0 ; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator