Codeforces #165 div1-C,div2-E Flawed Flow

http://www.codeforces.com/contest/269/problem/C

問題概要

N頂点、M辺のグラフが与えられ、頂点1がソース、Nがシンクである
ソースからシンクへの最大フローを流した時の、辺に流れた流量が辺ごとに与えられる(向きは与えられない)
フローが成り立つようにそれぞれの辺について向きを決めよ
ただし、得られるフローはサイクルを含んではいけない
グラフは連結で、答えは必ず存在する

N,M<=2*10^5
1<=流量<=10^4

方針

サイクルを含まないので、得られるフローのグラフは、トポロジカル順序をつけることが出来る。
ソースは最も順序の早い点で、そこから出る辺はすべてソースと逆向きに流れている
ここで、ソースに隣接する点のうち、どれかはトポロジカル順序がソースの次に小さいはずである
トポロジカル順序がソースの次に小さい頂点をvと置くと、vにはソース以外からフローが流れこまないので、
ソースから向かう辺の流量と、それ以外のつながれた辺の流量が等しいはず
逆に、ソース->vの辺以外はvから流れださなければフローが成立しないので、
ソースの時と同様にvから流す

残った頂点の中でトポロジカル順序が最も早いものが必ず見つかるはずなので、これを繰り返せば答えが求まる。

ソース、シンクの扱いに注意

O(N+M)

using namespace std;
static const int INF =500000000;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
int n,m;
vector<pair<pi,pi> > g[200005];
int in[200005],flow[200005];
int vis[200005];
int ans[200005];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b;
		g[a].push_back(make_pair(make_pair(b,c),make_pair(0,i)));
		g[b].push_back(make_pair(make_pair(a,c),make_pair(1,i)));
		flow[a]+=c;
		flow[b]+=c;
	}

	memset(ans,-1,sizeof(ans));

	queue<int> q;q.push(0);
	while(!q.empty()){
		int v=q.front();q.pop();
		vis[v]=1;
		for(int i=0;i<g[v].size();++i){
			pair<pi,pi>& e=g[v][i];
			if(vis[e.first.first]) continue;
			in[e.first.first]+=e.first.second;
			ans[e.second.second]=e.second.first;
			if(in[e.first.first]==flow[e.first.first]/2 && e.first.first!=n-1) q.push(e.first.first);
		}
	}


	for(int i=0;i<m;++i) printf("%d\n",ans[i]);





	return 0;
}