最大マッチング
- 色々な種類のマッチング問題があるが、大体調べれば多項式時間で解けるアルゴリズムがでてくる
- 二部最大マッチング
- 最大流問題に帰着できる(O(V^2E)かO(E*maxflow))
- 二部グラフの最大マッチング=最小頂点被覆 問題
- 二部グラフの被覆問題は最大マッチングに帰着できる(復元もできる)
- 色々な応用が紹介されていて、O(VE)とO(Esqrt(V))のアルゴリズムがある
- DinicでやってもO(Esqrt(V))が達成できる? これの解説
- 重み付き二部最大マッチング
- 最小費用流に帰着できる
- 一般最大マッチング
- 重み付き一般最大マッチング
- 他
- 「隣接セル通しのマッチング問題を考えるときに、(x+y)の偶奇で二部グラフに持ち込むテクがある」 出典
- 増加路で最大二部マッチングを求める手法がある 問題 解説
問題
二部最大マッチング
- ARC092 2D Plane 2N Points
- AOJ 1163 Cards
- yukicoder No.241 出席番号(1)
- yukicoder No.421 しろくろチョコレート
- 天下一プログラマーコンテスト2015予選A C. 天下一美術館 解説1 解説2
- ARC013 D. 切り分けできるかな?
- CSA66 Flipping Matrix 解説
- CSA23 No Prime Sum 解説(最小点被覆)
- HR Drawing Rectangles(最小点被覆)
- AC Maxmin Tour
重み付き二部最大マッチング
- AOJ 2429 まるかいて (重み最小化)
一般最大マッチング
重み付き一般最大マッチング
- yukicoder No.519 アイドルユニット (重み最大化)
- ARC080 Prime Flip (重み最小化)