プログラミングコンテストチャレンジブック 3-6 その2
3-6 ネットワークフローの続きです。今日は1トピックだけ。
- 二部マッチング
- 「仕事の割りあて」
- ノードが2つの種類に分かれていて、それぞれの種類の間の対応を辺で表現
- 端点(ノード)を共有しない辺の集合を「マッチング」といいその要素数が最大なものを「最大マッチング」と呼ぶ
- 始点、終点のノード s, t を追加して、s から全ての U のノードへ、全ての V のノードから t へ容量1の辺を貼ったグラフつくって最大流量を考えればいい
3-6 ネットワークフローの続きです。今日は1トピックだけ。