Cod sursa(job #319394)

Utilizator syntax_errorGustav Matula syntax_error Data 31 mai 2009 17:43:15
Problema Flux maxim Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;
typedef vector< int > :: iterator vit;

#define MAXN 1005
#define MAXM 2005

int N, M;
int V[ MAXN ];
int D[ MAXN ];
int dad[ MAXN ];
int Net[ MAXN ][ MAXN ];
vector< int > G[ MAXN ];

int cookie;

inline void fixflow( int x ) {
   for( int son = N; son >= 0; son = dad[ son ] ) {
      Net[ dad[ son ] ][ son ] -= x;
      Net[ son ][ dad[ son ] ] += x;
   }
}

queue< int > Q;

inline int BFS() {
   memset( D, 0, sizeof D );
   memset( dad, -1, sizeof dad );
   
   while( !Q.empty() ) Q.pop(); Q.push( 1 ); 
   V[1] = cookie; D[1] = 1000000000;
   
   while( !Q.empty() ) {
      int C = Q.front(); Q.pop();
      
      if( C == N ) { fixflow( D[N] ); return D[ N ]; }
      
      for( vit i = G[C].begin(); i != G[C].end(); ++i ) {
         if( V[*i] == cookie ) continue;
         if( Net[C][*i] <= 0 ) continue;
         
         dad[ *i ] = C;
         V[*i] = cookie; Q.push( *i );
         D[*i] = min( D[C], Net[C][*i] );
      }
   }
   
   return 0;
}

inline int maxflow() {
   memset( V, 0, sizeof V );
   int ret, flow; cookie = 1; 
   for( ret = 0; ( flow = BFS() ) != 0; ret += flow, ++cookie );
   return ret;
}

int main( void )
{
   freopen( "maxflow.in", "r", stdin );
   freopen( "maxflow.out", "w", stdout );
   
   scanf( "%d%d", &N, &M );
   for( int i = 0; i < M; ++i ) {
      int A, B, C; scanf( "%d%d%d", &A, &B, &C );
      
      Net[ A ][ B ] = C;
      G[ A ].push_back( B );
   }
   
   printf( "%d\n", maxflow() );
   
   return 0;
}