二部グラフの最大マッチングを求める際に自然に使える手法はどれか？ 2025.09.22 二部グラフの最大マッチングを求める際に自然に使える手法はどれか？ プリム法（最小全域木） ダイクストラ法（最短経路） クラスカル法（最小全域木） 最大流への還元（フローアルゴリズム） 二部マッチングは左部と右部をそれぞれ頂点集合とみなし、源点から左部へ、右部から終点へ容量1の辺を張り、元の辺に容量1を与えることで最大流問題に還元できます。これによりFord-FulkersonやDinicなどの最大流アルゴリズムを用いると最大マッチングが求まります。これは二部特有の標準解法の一つです。 クイズタグ: 競技プログラミング関連記事 競技プログラミングクイズ！【問題 全10問・答え付き】 | 2025年09月版
