ABC009 D - 浮気予防

D - 浮気予防
提出コード
最小カットの問題に初めて触れました。
まずは、女の子と高橋君を頂点、友人関係を辺としたグラフを作成します。
そして、頂点0からへ繋がるパスが存在しなくなるような辺の切り方を考えることになります。
ここで、複数のゴールがあるとわかりづらくなってしまうので、全てのから、新しく作成したn+1個目の頂点への辺を作成します。すると、からn+1の頂点へつながる辺を切るということは、ログインできなくする、という操作と同じものになります。
今は無向グラフになっていますが、これを、2つの有向グラフのあつまりとしてみると、始点が0、終点がn+1の最小カット問題に帰着させることができます。