操作:辺の向きをflip
AtCoder
AOJ
JAG
JAG模擬地区
AOJ-ICPC
AOJ-ICPC600点
フロー
グラフ
操作:辺の向きをflip
操作:flip
グラフのconnectivity
最適化テク:とりあえず元の問題の最適解を求める
最適解の数え上げ
BFS
けんちょん本演習問題
最適化テク:最適解に必ず含まれる要素を列挙する
DFS木やBFS木を考察する
思わず解きたくなる興味深い良問
【問題集】フローのステップアップ
ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね！！ 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…
AOJ
JAG
AOJ-ICPC450点
フロー
グラフ
操作
操作:辺の向きをflip
復元
AOJ-ICPC
JAG夏合宿
【問題集】フローの入門
そのまま覚えたいシンプル設定の中堅以上の典型問題
思わず解きたくなる興味深い良問
最大流問題の構造についての理解を問ういい感じの問題！ 問題へのリンク 問題概要 頂点数 、辺数 の単純有向グラフが与えられる (すべての辺の容量は 1)。2 点 間の最大フロー (辺素パスの本数) について考える。 今、いくつかの辺を選んで向きを反転するこ…
Codeforces
場合分け
2^K
添字のとりうる範囲がlogオーダー
Dijkstra法
最短路問題
DP値:ペア値
DP
グラフ
操作:辺の向きをflip
グラフテク:頂点を倍加する
パリティ
コーナーケース
2回やる意味はない
CodeforcesDIV1-C
CodeforcesR2400
AOJ-ICPC みを感じる！ 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。頂点 1 から頂点 へとたどり着きたい。以下の 2 種類の操作ができる。 頂点 上にいるとき、辺 をたどって、頂点 へと移動する 移動に要するコストは 1 任意の頂点に…
AOJ
HUPC
フロー
グラフ
必要条件を列挙したら十分条件になる
連結成分
強連結成分分解
DAG
グラフのconnectivity
最短路問題
操作:flip
操作:辺の向きをflip
多点を扱う問題
コーナーケース
強連結成分を考える
思わず解きたくなる興味深い良問
【問題集】フローのチャレンジ
こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…
