読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

AOJ2067 Flame of Nucleus

最大フロー AOJ

問題

Flame of Nucleus | Aizu Online Judge
頂点数N、枝数Mの重み付き単純無向グラフが与えられる。枝i(i=1, ..., M)の重みD_iは頂点間を移動する日数を表す。
現在の頂点i(i=1, ..., N)に滞在している人数P_iが与えられる。頂点i(i=1, ..., N)にL日後にK_i人以上住んでいる場合、K_i人以外は死ぬとする。
最適に移動した場合、最大何人生き残れるか?

制約

 1 \le N \le 100\\
1 \le L, D_i \le 10^4\\
1 \le P_i, K_i \le 10^6

解法

最大フローで解ける。
移動前と移動後のそれぞれの頂点と、sourceとsinkを表す2N+2個の頂点を用意する。
sourceと移動前の頂点i(i=1, ..., N)を容量P_iの枝で繋ぎ、移動後の頂点i'(i'=1, ..., N)とsinkを容量K_i'の枝で繋ぐ。さらに、頂点iから頂点jにL日以内で移動できる場合は、移動前の頂点iから移動後の頂点jに容量INFの枝を繋ぐ。L日以内で移動可能かどうかは、Warshall–Floydで全点対最短距離を求めておいて、それがL以下かどうかを見ればよい。
後は最大フローを求めればその値が答えとなる。

計算量

 O(N^3)+最大フローの計算量
最大フローはFord-Fulkersonでも十分に間に合う。

コード

最大フローは最大でも10^8で、全点対最短距離も最大10^6だからintで大丈夫。
下記では、移動前の頂点を0〜N-1、移動後の頂点をN〜2N-1、sourceを2N、sinkを2N+1とした。

感想

人の移動に最大フローが使えることはこの問題(Codeforces Round #304 (Div. 2) E. Soldier and Traveling)で知っていた。この問題はフローの復元とかあるし、良い類題になると思う。
なんか問題が読みにくかった気がする(reachの意味が不明瞭な気がする)