Codeforces #165 Div1. C. Flawed Flow

Div2ならEになる問題。ここまで解ければDiv2は余裕のはず…。
ということでCにチャレンジ。
http://codeforces.com/contest/269/problem/C

問題

辺あたりの容量がついた無向グラフが与えられる。
このグラフの始点から終点に対し、すべての辺を使って最大フローが流せることがわかっているとき、各辺の向きを答える。

解法

閉路がなく、かつ全部の辺を使えることがわかっているのがミソ。
よって、始点と終点以外は、その点についた全辺の容量の合計の半分が入力、半分が出力になる。
始点は必ず出力方向しか持たないため、その隣接点のうちに始点からの入力だけで全辺の容量の半分を使い果たす点がある。
（そういう点が無いなら、隣接点同士がすべて入力と出力を持つので閉路ができてしまう）

ここから、始点から初めて入力量が全辺の半分に達した点をBFSで探し、その点からの残りの辺はすべて出力とみなしていけばよい。
計算量としては、O(V+E)なのでV,E<=200000でもなんとか終わる。

int N,M;
int dir[200002];
vector<pair<int,pair<int, ll> > > E[200001];
ll LF[200001];
int vis[200002];

void solve() {
	int f,r,i,j,k,l;
	
	GET2(&N,&M);
	FOR(i,M) {
		j=GETi()-1;
		k=GETi()-1;
		l=GETi();
		E[j].push_back(make_pair(k,make_pair(i+1,l)));
		E[k].push_back(make_pair(j,make_pair(-(i+1),l)));
		LF[j]+=l;
		LF[k]+=l;
	}
	
	LF[0]=LF[N-1]=0;
	for(i=1;i<=N-2;i++) LF[i]/=2;
	queue<int> q;
	q.push(0);
	
	while(!q.empty()) {
		int cur=q.front();
		q.pop();
		vis[cur]=1;
		FOR(i,E[cur].size()) {
			int tar=E[cur][i].first;
			if(vis[tar]) continue;
			
			if(E[cur][i].second.first < 0) dir[-E[cur][i].second.first]=1;
			else dir[E[cur][i].second.first]=0;
			
			LF[tar] -= E[cur][i].second.second;
			if(tar!=N-1 && LF[tar]==0) q.push(tar);
		}
	}
	
	for(i=1;i<=M;i++) _P("%d\n",dir[i]);
	
	return;
}

まとめ

今回は解説を見てしまった。
でも、自分ではすべての辺を使い切るという条件から「半分は入力で半分は出力」というところに考えが及ばなかったな…。