グラフの辺数削減テク:ある最適解に含まれ得る辺以外を削除する
AOJ
RUPC
最適化テク:自明な上界が最適解
フロー
グラフ
最短路問題
最小カット
最適化テク:解に確実に含まれる要素を列挙する
グラフの辺数を削減する
けんちょん本演習問題
Floyd-Warshall法
前処理
前処理:Floyd-Warshall法
DAG
【問題集】フローの入門
そのまま覚えたいシンプル設定の中堅以上の典型問題
グラフの辺数削減テク:ある最適解に含まれ得る辺以外を削除する
「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…
AOJ
ICPCアジア
AOJ-ICPC450点
最小全域木
グラフ
最適化テク:解に確実に含まれる要素を列挙する
最適化テク:制約条件を加えて探索候補を絞る
グラフの辺数を削減する
最適化テク:とりあえず元の問題の最適解を求める
AOJ-ICPC
けんちょん本演習問題
そのまま覚えたい典型問題
思わず解きたくなる興味深い良問
グラフの辺数削減テク:ある最適解に含まれ得る辺以外を削除する
とても面白い問題です！ 問題へのリンク 問題概要 頂点数 、辺数 の、連結な重み付き無向単純グラフ が与えられる。 このグラフの「最小全域木」はさまざまなものが考えられるが、そのすべてに含まれるような辺の集合を考える。 その集合の要素数と、その集…
グラフ
グラフの辺数を削減する
最小全域木
ラグランジュ緩和
密グラフ
二分探索
N個からK個を選ぶ設定の問題
CSAcademy
全域木を考える
個人的要復習
制約条件:グラフの次数列
NP困難(特殊構造なので解ける)
高度典型
マルチテストケース問題
AlienDP
グラフの辺数削減テク:ある最適解に含まれ得る辺以外を削除する
ラグランジュ緩和か、、、 しかしこれ、ある特定の 1 頂点について次数が 以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白い。 全域最小木スライドにある通り、全頂点について次数が 以下となるような最小全域木を求…
