KUPC 2014 I - Rain

問題

n個の地域に雨を同じ量ずつ振らせたい。
雨の降らせ方はm個あって、
i番目の降らせ方ではa[i]番目の地域に2, b[i]番目の地域に0, それ以外の全ての地域に1の雨が降る。

最初、上の降らせかたで、c0, ... , ck-1の雨を降らせた。
この後、どうにかして全ての地域に降る雨の量を同じにしたい。
最小で何回雨を降らせればそれが達成できるか。できないときは-1を出力せよ。

制約条件

n≦10000
m≦20000
k≦15

方針

最小費用流。
等しくするだけなので、雨の量は差分だけを考えてよくて、
i番目の降らせかたはa[i]番目に+1, b[i]番目に-1, 残りの地域を+0としても同じ。

k個の初期雨が終わった時点で、
x0, x1, ..., xn-1の雨になっているとすると、
プラスのところを0まで減らして、マイナスのところを0まで増やす必要がある。

n頂点+ソースとシンクからなるグラフを考える。
プラスのxiには、ソースからコスト0, 流量xiの辺を張って、
マイナスのxiには、シンクへコスト0, 流量|xi|の辺を張る。

b[i]からa[i]にコスト1, 流量無限の辺を張れば、このグラフにΣ|xi|のフローを流すときの最小コストが、必要な雨の回数の最小値である。

グラフが大きいけど、流量が高々15くらいしかないので間に合う。
(15回のダイクストラが間に合えばよい)

ソースコード

int main(){
	
	int n, m, k;
	cin >> n >> m >> k;
	vi v(k);
	vi a(m), b(m), c(m), cnt(n);
	costflowGraph<int> g(n + 2);
	
	int s = n, t = n + 1, f = 0;
	
	rep(i, k) cin >> v[i];
	rep(i, m){
		cin >> a[i] >> b[i] >> c[i];
		a[i]--; b[i]--;
		
		g.add(b[i], a[i], inf, c[i]);
	}
	
	rep(i, k){
		v[i]--;
		cnt[a[v[i]]]++;
		cnt[b[v[i]]]--;
	}
	rep(i, n){
		if(cnt[i] < 0) g.add(i, t, -cnt[i], 0);
		if(cnt[i] > 0) g.add(s, i, cnt[i], 0), f += cnt[i];
	}
	
	cout << g.min_cost_flow(s, t, f) << endl;
	
	return 0;
}