けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

グラフを変形する問題

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

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