hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 最大マッチング 色々な種類のマッチング問題があるが、大体調べれば多項式時間で解けるアルゴリズムがでてくる 二部最大マッチング 最大流問題に帰着できる（O(V^2E)かO(E*maxflow)） 二部グラフの最大マッチング＝最小頂点被覆 問題 二部グラフの被覆問題は最大マッチングに帰着できる（復元もできる） 色々な応用が紹介されていて、O(VE)とO(Esqrt(V))のアルゴリズムがある DinicでやってもO(Esqrt(V))が達成できる？ これの解説 重み付き二部最大マッチング 最小費用流に帰着できる 一般最大マッチング O(N^3) 重み付き一般最大マッチング O(N^2M) or O… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F05%2F09%2F120253" title="競技プログラミングにおける最大マッチング問題まとめ - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-05-09 12:02:53 rich https://blog.hamayanhamayan.com/entry/2017/05/09/120253 1.0 100%