プログラミングコンテストチャレンジブック 3-6 その2

3-6 ネットワークフローの続きです。今日は1トピックだけ。

  • 二部マッチング
    • 「仕事の割りあて」
    • ノードが2つの種類に分かれていて、それぞれの種類の間の対応を辺で表現
    • 端点(ノード)を共有しない辺の集合を「マッチング」といいその要素数が最大なものを「最大マッチング」と呼ぶ
    • 始点、終点のノード s, t を追加して、s から全ての U のノードへ、全ての V のノードから t へ容量1の辺を貼ったグラフつくって最大流量を考えればいい