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

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