BoxerTC

Untitled

Jun 18th, 2015
583
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.44 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sc( x ) scanf( "%d" , &x )
  5. #define REP( i , n ) for( int i = 0 ; i < n ; ++i )
  6. #define clr( t , val ) memset( t , val , sizeof( t ) )
  7.  
  8. #define pb push_back
  9. #define all( v ) v.begin() , v.end()
  10. #define SZ( v ) ((int)(v).size())
  11.  
  12. #define mp make_pair
  13. #define fi first
  14. #define se second
  15.  
  16. typedef vector< int > vi;
  17. typedef long long ll;
  18. typedef pair< int , int > pii;
  19.  
  20. #define MAXV 1000
  21. #define MAXE 300000
  22. #define INF (1<<30)
  23.  
  24. typedef long long ll;
  25.  
  26. // Dinic algorithm for max flow
  27. int n , s , t , E;
  28. int to[ 2*MAXE + 5 ] , cap[ 2*MAXE + 5 ] , next[ 2*MAXE + 5 ];
  29. int last[ MAXV + 5 ] , now[ MAXV + 5 ] , dist[ MAXV + 5 ];
  30. void add_edge( int u , int v , int uv , int vu = 0 ){
  31.     to[ E ] = v ; cap[ E ] = uv ; next[ E ] = last[ u ] ; last[ u ] = E ++;
  32.     to[ E ] = u ; cap[ E ] = vu ; next[ E ] = last[ v ] ; last[ v ] = E ++;
  33. }
  34. bool bfs(){
  35.     REP( i , n ) dist[ i ] = INF;
  36.     queue< int > Q;
  37.     dist[ t ] = 0;
  38.     Q.push( t );
  39.     while( !Q.empty() ){
  40.         int u = Q.front() ; Q.pop();
  41.         for( int e = last[ u ] ; e != -1 ; e = next[ e ] ){
  42.             int v = to[ e ];
  43.             if( cap[ e ^ 1 ] && dist[ v ] >= INF ){
  44.                 dist[ v ] = dist[ u ] + 1;
  45.                 Q.push( v );
  46.             }
  47.         }
  48.     }
  49.     return dist[ s ] < INF;
  50. }
  51. int dfs( int u , int f ){
  52.     if( u == t ) return f;
  53.     for( int &e = now[ u ] ; e != -1 ; e = next[ e ] ){
  54.         int v = to[ e ];
  55.         if( cap[ e ] && dist[ u ] == dist[ v ] + 1 ){
  56.             int ret = dfs( v  , min( f , cap[ e ] ) );
  57.             if( ret ){
  58.                 cap[ e ] -= ret;
  59.                 cap[ e ^ 1 ] += ret;
  60.                 return ret;
  61.             }
  62.         }
  63.     }
  64.     return 0;
  65. }
  66. ll maxFlow(){
  67.     ll flow = 0;
  68.     while( bfs() ){
  69.        
  70.         REP( i , n ) now[ i ] = last[ i ];
  71.         while( 1 ){
  72.             int f = dfs( s , INF );
  73.             if( !f ) break;
  74.             flow += f;
  75.         }
  76.     }
  77.     return flow;
  78. }
  79.  
  80. int L[ MAXE + 5 ] , R[ MAXE + 5 ] , orig[ MAXE + 5 ] , dest[ MAXE + 5 ];
  81. int main(){
  82.     //cooling.in
  83.        
  84.     freopen("cooling.in", "r", stdin);
  85.     freopen("cooling.out", "w", stdout);
  86.    
  87.     int nodes , edges;
  88.     while( sc( nodes ) == 1 ){
  89.         sc( edges );
  90.         vi ind( nodes );
  91.         REP( i , edges ){
  92.             int u , v , lo , hi;
  93.             sc( u ) , sc( v ) , sc( lo ) , sc( hi );
  94.             u -- , v --;
  95.             orig[ i ] = u , dest[ i ] = v;
  96.             L[ i ] = lo , R[ i ] = hi;
  97.             ind[ u ] += lo;
  98.             ind[ v ] -= lo;
  99.         }
  100.         n = nodes + 2;
  101.         s = n - 2 , t = n - 1;
  102.         E = 0;
  103.         REP( i , n ) last[ i ] = -1;
  104.         REP( i , edges )
  105.             add_edge( orig[ i ] , dest[ i ] , R[ i ] - L[ i ] ) ;
  106.         //For each v with d(v) < 0, add arc (s, v) with capacity -d(v).
  107.         //For each v with d(v) > 0, add arc (v, t) with capacity d(v).
  108.         REP( i , nodes )
  109.             if( ind[ i ] < 0 ) add_edge( s , i , - ind[ i ] );
  110.             else add_edge( i , t , ind[ i ] , 0 );
  111.         maxFlow();
  112.         bool solve = 1;
  113.         for( int e = last[ s ] ; e != -1 ; e = next[ e ] )
  114.             if( cap[ e ] ) {
  115.                 solve = 0;
  116.                 break;
  117.             }
  118.         puts( solve ? "YES" : "NO" );
  119.         if( !solve ) continue;
  120.         REP( i , edges ){
  121.             printf( "%d\n" , R[ i ] - cap[ 2 * i ] );
  122.         }
  123.     }
  124. }
Advertisement
Add Comment
Please, Sign In to add comment