Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

zkw流超时 , why ? 求大牛出手相助

Posted by shuaige123 at 2013-01-15 09:56:24 on Problem 2516
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator