Codeforces #188 Div1. C. Balance

この回はDよりCの方が回答者が少ない。
http://codeforces.com/contest/317/problem/C

問題

N個のVリットル入る器があり、初期状態でそれぞれA[i]リットルの水が入っている。

また、一部の器の間には管があり、整数リットル分の水を移動できる。
もちろん途中で水がVリットルを超えてはいけない。

2*N^2以下の回数だけ水の移動を行い、各器の水の容量をB[i]にせよ。

解法

目的のB[i]より水が多い器iと、B[j]より水が少ない器jのペア(i,j)を考える。
ただし、(i,j)は複数の管を使い水を移動可能とする。

この時、差分の最小値であるd=min(A[i]-B[i],B[j]-A[j])の水の量だけiからjにdだけ水を流して行く、という処理を各(i,j)について行えばよい。

ただ、途中でVを超えてしまってはいけないので、次のようにすればよい。
i→k→...→jという水を流すパスがあるとする。

• k番目の器にdリットル入れる余裕があるなら、i→kにdリットル流し、あとは同様に(k,j)の間にdリットル流す
• k番目の器にdリットル入れる余裕がないなら、i→kにまずkがVリットル満タンになるまで流した後、(k,j)の間にdリットル流し、最後にまたi→kに残りの分の水を流す

こうすると、i→jにいたるパスの長さLに対し、2Lステップで水dを流せる。

上記処理を終え、A[i]が全部B[i]になっていればよい。

int N,V,E;
int mat[301][301];
int A[301],B[301];
vector<pair<pair<int,int>,int> > R;

void flow2(vector<int>& P,int si,int ti,int d) {
	int i;
	if(si==ti) return;
	if(A[P[si+1]]+d <= V) {
		A[P[si]]-=d;
		A[P[si+1]]+=d;
		R.push_back(make_pair(make_pair(P[si],P[si+1]),d));
		flow2(P,si+1,ti,d);
	}
	else {
		int d2 = V-A[P[si+1]];
		A[P[si]]-=d2;
		A[P[si+1]]+=d2;
		if(d2>0) R.push_back(make_pair(make_pair(P[si],P[si+1]),d2));
		flow2(P,si+1,ti,d);
		A[P[si]]-=d-d2;
		A[P[si+1]]+=d-d2;
		R.push_back(make_pair(make_pair(P[si],P[si+1]),d-d2));
	}
}

int flow(int s,int t,int d) {
	int i,j,y;
	vector<int> P;
	P.push_back(s);
	for(i=s;i!=t;) {
		FOR(y,N) if(mat[i][y]==1 && mat[y][t]==mat[i][t]-1) break;
		P.push_back(i=y);
	}
	
	flow2(P,0,P.size()-1,d);
}

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N>>V>>E;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	FOR(x,N) FOR(y,N) mat[x][y]=9999;
	FOR(x,N) mat[x][x]=0;
	FOR(i,E) {
		cin>>x>>y;
		mat[x-1][y-1]=mat[y-1][x-1]=1;
	}
	FOR(i,N) FOR(j,N) FOR(k,N) mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k]);
	FOR(x,N) FOR(y,N) {
		if(mat[x][y]>N) continue;
		j = min(A[x]-B[x],B[y]-A[y]);
		if(j<=0) continue;
		flow(x,y,j);
	}
	
	FOR(x,N) if(A[x]!=B[x]) return (void)_P("NO\n");
	_P("%d\n",R.size());
	FOR(i,R.size()) _P("%d %d %d\n",R[i].first.first+1,R[i].first.second+1,R[i].second);
}

まとめ

水の上限Vリットルがあっても、2Lステップあれば上限無視してdリットル流せるというのがわかったのが収穫。