Codeforces #453 Div1 D. Weighting a Tree

これは頑張ってもよかったかもな…。
http://codeforces.com/contest/901/problem/D

問題

N頂点M辺のグラフが与えられる。
各頂点iにはパラメータC[i]が振られている。
なお、パラメータの偶奇と辺の数の偶奇は一致する。

この状態で、各辺に-2N^2～2N^2の範囲の整数を設定し、各頂点のパラメータと、辺の設定値の総和を一致させることができるか。
可能ならその一例を示せ。

解法

まずグラフが二部グラフである場合を考える。
この時、辺に整数を設定すると両グループの頂点に同じだけ設定値が影響する。
よって、両グループの頂点のパラメータの総和が一致していなければならない。

逆に一致していれば、必ず条件を満たす辺の設定値がある。
このグラフのSpanning Treeを考え、次数1の頂点から順につながる辺の重みを設定していけばよい。

次に二部グラフでない場合を考える。
上記同様にSpanning Treeを考え、二部グラフとみなそう。
この時両グループの頂点のパラメータの総和が一致するなら、上と同様に処理できる。
そうでない場合、このグラフが二部グラフでないなら、Spanning Treeに含まれない辺で、二部グラフの同グループの頂点同士を結ぶ辺が１つは存在する。
この辺に適切な設定値を割り当て、両グループの残りパラメータの総和を一致させよう。
あとは同じ。

int N,M;
ll C[101010];
int U[101010],V[101010];
vector<pair<int,int>> E[101010];
ll R[101010];
int col[101010];
ll P[2];
int tree[101010];
int in[101010];

void dfs(int cur,int c) {
	col[cur]=c;
	P[c]+=C[cur];
	FORR(e,E[cur]) {
		if(col[e.first]==-1) {
			tree[e.second]=1;
			dfs(e.first,c^1);
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>C[i];
	FOR(i,M) {
		cin>>U[i]>>V[i];
		U[i]--,V[i]--;
		E[U[i]].push_back({V[i],i});
		E[V[i]].push_back({U[i],i});
	}
	MINUS(col);
	dfs(0,0);
	
	if(P[0]!=P[1]) {
		FOR(i,M) if(col[U[i]]==col[V[i]]) break;
		if(i==M) return _P("NO\n");
		R[i]=(P[col[U[i]]]-P[col[U[i]]^1])/2;
		C[U[i]]-=R[i];
		C[V[i]]-=R[i];
	}
	
	queue<int> Q;
	FOR(i,N) {
		FORR(e,E[i]) if(tree[e.second]) in[i]++;
		if(in[i]==1) Q.push(i);
	}
	while(Q.size()) {
		
		int cur=Q.front();
		Q.pop();
		
		int id=-1;
		FORR(e,E[cur]) if(tree[e.second]) id=e.second;
		
		if(id>=0) {
			int op=U[id]+V[id]-cur;
			R[id]=C[cur];
			tree[id]=0;
			C[cur]=0;
			C[op]-=R[id];
			in[op]--;
			if(in[op]==1) Q.push(op);
			
		}
		
	}
	
	cout<<"YES"<<endl;
	FOR(i,M) cout<<R[i]<<endl;
	
}

まとめ

パリティの条件からうまく二部グラフを思いつくべきだったな。
辺の設定値を頂点に影響させる問題では常に考えるようにしなくては。