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

最大マッチング 色々な種類のマッチング問題があるが、大体調べれば多項式時間で解けるアルゴリズムがでてくる 二部最大マッチング 最大流問題に帰着できる(O(V^2E)かO(E*maxflow)) 二部グラフの最大マッチング=最小頂点被覆 問題 二部グラフの被覆問題は最大マッチングに帰着できる(復元もできる) 色々な応用が紹介…