Codeforces ECR #045 : F. Flow Control

これ似たようなの見たことある気がするな。
http://codeforces.com/contest/990/problem/F

問題

連結無向グラフが与えられる。
各辺にいずれかの方向にフローの量を指定し、各頂点に与えられたフローの総入出力量を満たすようにせよ。

解法

総入出力量の全頂点の和が0でないとそもそも達成不可。
それ以外の場合、DFSでグラフを探索しよう。
探索後自身の頂点を抜ける際、自身の総入出力量をちょうど達成するように親頂点からフローを流す処理を繰り返すと、順次葉頂点から条件を満たすことができる。

int N,M;
map<pair<int,int>,int> ID;
set<int> E[202020];
int F[202020];
int ret[202020];
int vis[202020];

void dfs(int cur) {
	vis[cur]=1;
	FORR(e,E[cur]) if(vis[e]==0) {
		dfs(e);
		F[cur]+=F[e];
		if(ID[{cur,e}]>0) ret[ID[{cur,e}]]=F[e];
		else ret[-ID[{cur,e}]]=-F[e];
		F[e]=0;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll sum=0;
	FOR(i,N) {
		cin>>F[i];
		sum+=F[i];
	}
	if(sum) return _P("Impossible\n");
	cin>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x].insert(y);
		E[y].insert(x);
		ID[{x,y}]=i+1;
		ID[{y,x}]=-(i+1);
	}
	dfs(0);
	
	
	cout<<"Possible"<<endl;
	FOR(i,M) cout<<ret[i+1]<<endl;
}

まとめ

解いてる人少ないけど、コードも考え方もシンプル。