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

マッチング 色々な種類のマッチング問題があるが、大体調べれば多項式時間で解けるアルゴリズムがでてくる 1. 二部最大マッチング 2. 重み付き二部最大マッチング 3. 一般最大マッチング O(N^3) 4. 重み付き一般最大マッチング O(N^2M) or O(N^3) 二部最大マッチングは最大流問題として実装でき、重…