AOJ2067 Flame of Nucleus
問題
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人以外は死ぬとする。
最適に移動した場合、最大何人生き残れるか?
制約
解法
最大フローで解ける。
移動前と移動後のそれぞれの頂点と、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以下かどうかを見ればよい。
後は最大フローを求めればその値が答えとなる。
計算量
最大フローは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の意味が不明瞭な気がする)