Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Mar 13th, 2018 58 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include <cstdio>
  2.  
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef long long llint;
  8.  
  9. const int MAXN = 5000;
  10. const int MAXM = 30000;
  11. const int MAXE = 2*MAXM;
  12.  
  13. int n, m, e;
  14. int src, sink;
  15.  
  16. int last[MAXN], dist[MAXN], curr[MAXN];
  17. int next[MAXE], cap[MAXE], adj[MAXE];
  18.  
  19. void make_edge( int a, int b, int c ) {
  20.   adj[e] = b;
  21.   cap[e] = c;
  22.   next[e] = last[a];
  23.   last[a] = e++;
  24. }
  25.  
  26. bool init_graph() {
  27.   for( int i = 0; i < n; ++i ) {
  28.     curr[i] = last[i];
  29.     dist[i] = -1;
  30.   }
  31.  
  32.   queue<int> Q;
  33.   Q.push( src );
  34.   dist[src] = 0;
  35.  
  36.   while( !Q.empty() ) {
  37.     int x = Q.front(); Q.pop();
  38.  
  39.     for( int e = last[x]; e != -1; e = next[e] ) {
  40.       if( cap[e] > 0 && dist[adj[e]] == -1 ) {
  41.         Q.push( adj[e] );
  42.         dist[adj[e]] = dist[x] + 1;
  43.       }
  44.     }
  45.   }
  46.  
  47.   return dist[sink] != -1;
  48. }
  49.  
  50. int push( int x, int flow ) {
  51.   if( x == sink ) return flow;
  52.  
  53.   for( int &e = curr[x]; e != -1; e = next[e] ) {
  54.     if( cap[e] == 0 || dist[x] + 1 != dist[adj[e]] ) continue;
  55.  
  56.     int f = push( adj[e], min( flow, cap[e] ) );
  57.     if( f > 0 ) {
  58.       cap[e] -= f;
  59.       cap[e^1] += f;
  60.       return f;
  61.     }
  62.   }
  63.  
  64.   return 0;
  65. }
  66.  
  67. llint dinic() {
  68.   llint ret = 0;
  69.   while( init_graph() ) {
  70.     for( ;; ) {
  71.       int f = push( src, 1000000000 );
  72.       if( f == 0 ) break;
  73.       ret += f;
  74.     }
  75.   }
  76.   return ret;
  77. }
  78.  
  79. int main( void ) {
  80.   scanf( "%d%d", &n, &m );
  81.  
  82.   for( int i = 0; i < n; ++i ) last[i] = -1;
  83.   for( int i = 0; i < m; ++i ) {
  84.     int a, b, c;
  85.     scanf( "%d%d%d", &a, &b, &c ); --a, --b;
  86.     make_edge( a, b, c );
  87.     make_edge( b, a, c );
  88.   }
  89.  
  90.   src = 0;
  91.   sink = n-1;
  92.   printf( "%lld\n", dinic() );
  93.  
  94.   return 0;
  95. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top