AtCoder Beginner Contest 010 D. 浮気予防
解法
各友人関係を容量1の枝で双方向に繋ぎ、高橋くんをsource、女の子から容量1で片方向につながれた頂点をsinkとするネットワークと考える。
ここで、各操作1が頂点間の枝を切断する操作であり、また、女の子以外に対して操作2を行う必要がないことを考えると、操作2は女の子とsinkを結ぶ枝を切断する操作であることがわかる。
この操作を最小にしたいということは、求める答えは、このネットワークの最小カットである。
よって最大フロー=最小カット定理により、このネットワークの最大フローを求めれば良い。
計算量
O((|E|+G)|N|^2)
コード
感想
2つ目の操作がない場合は、女の子とsinkを容量INFで繋げば良さそう?