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

n-knuu's logs

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

AtCoder Beginner Contest 010 D. 浮気予防

グラフ 最小カット AtCoder

解法

各友人関係を容量1の枝で双方向に繋ぎ、高橋くんをsource、女の子から容量1で片方向につながれた頂点をsinkとするネットワークと考える。
ここで、各操作1が頂点間の枝を切断する操作であり、また、女の子以外に対して操作2を行う必要がないことを考えると、操作2は女の子とsinkを結ぶ枝を切断する操作であることがわかる。
この操作を最小にしたいということは、求める答えは、このネットワークの最小カットである。
よって最大フロー=最小カット定理により、このネットワークの最大フローを求めれば良い。

計算量

O((|E|+G)|N|^2)

コード


感想

2つ目の操作がない場合は、女の子とsinkを容量INFで繋げば良さそう?