ABC010 D問題 浮気防止

abc010.contest.atcoder.jp

 グラフは実装が難しいね。

基本方針

 全ての友人関係は容量1の無向辺とみなせる。全てのp[i]からあるノードXに対して容量1の有向辺が張られていると考えれば、この問題は最小カット問題に帰着できる。最小カット問題は最大フロー問題と等価なので、構築したグラフに対する最大フロー問題を解く。

具体的な方針

 Ford-Fulkerson法を実装する。やることは、流れなくなるまで貪欲に始点から終点にかけてフローを流していくだけ。これはDFSで楽に実装できる。ただし、フローを押し戻すような流れを考えなければいけない。

 具体的には、ある流量fのフローがあって、ノードAからBにかけて流れていくとき、新たにBからAに対して流量fのフローが流れる余地が生まれたと考え、グラフを更新していく。こうすることによって、貪欲にDFSを回すだけで最大流が求められるようになる。計算量は、最大流をF、辺の本数をEとしてO(FE)。

 ネット上にいくつか解説しているサイトがあるけど、蟻本が一番わかりやすかった。実装もほとんど蟻本のまま。

実装

abc010.contest.atcoder.jp

感想

 グラフの問題は重たい。早いところ実装に慣れてしまいたい。