典型的な二部マッチングの問題です。 問題へのリンク 問題概要 枚の赤いカードと、 枚の青いカードとの間でマッチングを作っていきます。 各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができます。 最大マッチン…

AOJ 1163 カードゲーム (ICPC 国内予選 2009 E) (400 点)

ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね！！ 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…

AOJ 2594 Reverse a Road II (JAG 模擬地区 2014 F) (600 点)

「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…

AOJ 2872 最短距離を伸ばすえびちゃん (RUPC 2018 day3-F)