グラフを変形する問題
AOJ
RUPC
自明な上界が最適解
フロー
グラフ問題
最短路問題
グラフを変形する問題
最小カット
解に確実に含まれる要素を列挙する
グラフの考えるべき辺数を減らす
けんちょん本演習問題
Floyd-Warshall法
前処理
前処理:Floyd-Warshall法
DAG
「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…