はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるマッチング問題まとめ

マッチング

1. 二部最大マッチング
2. 重み付き二部最大マッチング
3. 一般最大マッチング
4. 重み付き一般最大マッチング

  • 二部最大マッチングは最大流問題として実装でき、重み付き二部最大マッチングは最小費用流問題として実装できる
  • 一般マッチングの実装
  • 「隣接セル通しのマッチング問題を考えるときに、(x+y)の偶奇で二部グラフに持ち込むテクがある」 出典
  • 二部グラフの最大マッチング=最小頂点被覆 問題
  • 色々な応用が紹介されている