Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define sc( x ) scanf( "%d" , &x )
- #define REP( i , n ) for( int i = 0 ; i < n ; ++i )
- #define clr( t , val ) memset( t , val , sizeof( t ) )
- #define pb push_back
- #define all( v ) v.begin() , v.end()
- #define SZ( v ) ((int)(v).size())
- #define mp make_pair
- #define fi first
- #define se second
- typedef vector< int > vi;
- typedef long long ll;
- typedef pair< int , int > pii;
- #define MAXV 1000
- #define MAXE 300000
- #define INF (1<<30)
- typedef long long ll;
- // Dinic algorithm for max flow
- int n , s , t , E;
- int to[ 2*MAXE + 5 ] , cap[ 2*MAXE + 5 ] , next[ 2*MAXE + 5 ];
- int last[ MAXV + 5 ] , now[ MAXV + 5 ] , dist[ MAXV + 5 ];
- void add_edge( int u , int v , int uv , int vu = 0 ){
- to[ E ] = v ; cap[ E ] = uv ; next[ E ] = last[ u ] ; last[ u ] = E ++;
- to[ E ] = u ; cap[ E ] = vu ; next[ E ] = last[ v ] ; last[ v ] = E ++;
- }
- bool bfs(){
- REP( i , n ) dist[ i ] = INF;
- queue< int > Q;
- dist[ t ] = 0;
- Q.push( t );
- while( !Q.empty() ){
- int u = Q.front() ; Q.pop();
- for( int e = last[ u ] ; e != -1 ; e = next[ e ] ){
- int v = to[ e ];
- if( cap[ e ^ 1 ] && dist[ v ] >= INF ){
- dist[ v ] = dist[ u ] + 1;
- Q.push( v );
- }
- }
- }
- return dist[ s ] < INF;
- }
- int dfs( int u , int f ){
- if( u == t ) return f;
- for( int &e = now[ u ] ; e != -1 ; e = next[ e ] ){
- int v = to[ e ];
- if( cap[ e ] && dist[ u ] == dist[ v ] + 1 ){
- int ret = dfs( v , min( f , cap[ e ] ) );
- if( ret ){
- cap[ e ] -= ret;
- cap[ e ^ 1 ] += ret;
- return ret;
- }
- }
- }
- return 0;
- }
- ll maxFlow(){
- ll flow = 0;
- while( bfs() ){
- REP( i , n ) now[ i ] = last[ i ];
- while( 1 ){
- int f = dfs( s , INF );
- if( !f ) break;
- flow += f;
- }
- }
- return flow;
- }
- int L[ MAXE + 5 ] , R[ MAXE + 5 ] , orig[ MAXE + 5 ] , dest[ MAXE + 5 ];
- int main(){
- //cooling.in
- freopen("cooling.in", "r", stdin);
- freopen("cooling.out", "w", stdout);
- int nodes , edges;
- while( sc( nodes ) == 1 ){
- sc( edges );
- vi ind( nodes );
- REP( i , edges ){
- int u , v , lo , hi;
- sc( u ) , sc( v ) , sc( lo ) , sc( hi );
- u -- , v --;
- orig[ i ] = u , dest[ i ] = v;
- L[ i ] = lo , R[ i ] = hi;
- ind[ u ] += lo;
- ind[ v ] -= lo;
- }
- n = nodes + 2;
- s = n - 2 , t = n - 1;
- E = 0;
- REP( i , n ) last[ i ] = -1;
- REP( i , edges )
- add_edge( orig[ i ] , dest[ i ] , R[ i ] - L[ i ] ) ;
- //For each v with d(v) < 0, add arc (s, v) with capacity -d(v).
- //For each v with d(v) > 0, add arc (v, t) with capacity d(v).
- REP( i , nodes )
- if( ind[ i ] < 0 ) add_edge( s , i , - ind[ i ] );
- else add_edge( i , t , ind[ i ] , 0 );
- maxFlow();
- bool solve = 1;
- for( int e = last[ s ] ; e != -1 ; e = next[ e ] )
- if( cap[ e ] ) {
- solve = 0;
- break;
- }
- puts( solve ? "YES" : "NO" );
- if( !solve ) continue;
- REP( i , edges ){
- printf( "%d\n" , R[ i ] - cap[ 2 * i ] );
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment