CFR 269 C. Flawed Flow ( Flow )

Problem - 269C - Codeforces
izrak の提出見て回答。

題意：
給你一張無向圖，邊有容量，要求定向，使得有最大流。源點 1，匯點 N。

制約：
2 ≤ N ≤ 2e5
N - 1 ≤ M ≤ 2e5
C[ i ] ≤ 1e4

解法：
初始時對所有邊的端點添上該邊的容量。
為了要滿足流量守恆，也就是進來的流等於出去的流，所以進行 BFS，每次取出來更新人家的必須是已經守恆的。顯然源點一直都是守恆的，所以可以做為起點。拿來更新人家的這個節點有多少向外的流量，就有相應多的流量可以幫助其他未平衡的節點平衡。
最後決定邊的方向的是平衡的時間順序，如果有條邊 ( u, v )，那麼 u -> v 若且唯若 u 平衡地比 v 早。
以下 code 可以用 BFS 寫，只是這樣很潮。
rewind( stdin ) 好潮。雖然會變慢很多。

複雜度：
O( M )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 2e5 );

int N, M;
int tot_flow[ MAXN ];
vector< pair< int, int > > G[ MAXN ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < M; ++i ) {
    int u, v, w;
    cin >> u >> v >> w;
    tot_flow[ u - 1 ] += w;
    tot_flow[ v - 1 ] += w;
    G[ u - 1 ].emplace_back( w, v - 1 );
    G[ v - 1 ].emplace_back( w, u - 1 );
  }
  tot_flow[ 0 ] = tot_flow[ N - 1 ] = -1;
  static int done[ MAXN ];
  static int in_flow[ MAXN ];
  int dptr = 0;
  done[ dptr++ ] = 0;
  for( int i = 0; i < dptr; ++i ) {
    for( int j = 0; j < G[ done[ i ] ].size(); ++j ) {
      in_flow[ G[ done[ i ] ][ j ].second ] += G[ done[ i ] ][ j ].first;
      if( in_flow[ G[ done[ i ] ][ j ].second ] * 2 == tot_flow[ G[ done[ i ] ][ j ].second ] ) {
        done[ dptr++ ] = G[ done[ i ] ][ j ].second;
      }
    }
  }
  done[ dptr++ ] = N - 1;
  static int ts[ MAXN ];
  for( int i = 0; i < N; ++i ) {
    ts[ done[ i ] ] = i;
  }
  rewind( stdin ); // rewinds the scanner pointer back to the beginning
  cin >> N >> M;
  for( int i = 0; i < M; ++i ) {
    int u, v, w;
    cin >> u >> v >> w;
    cout << "01"[ ts[ v - 1 ] < ts[ u - 1 ] ] << "\n";
  }
  return 0;
}