頂点に容量があるフロー
AtCoder
旧ABC
青色diff
グラフ問題
グラフのconnectivity
フロー
最小カット
頂点に容量があるフロー
多点を1点として扱う
けんちょん本演習問題
最小回数
denseなグラフをスーパーノードでsparseにする
最小カットのよい練習問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられます。頂点番号を とします。また、頂点 0 以外の 個の頂点 が与えられます。 今、次の操作を行っていくことで、頂点 0 からは頂点 のいずれにも到達で…
AtCoder
AtCoder800点
ARC-F
フロー
グラフ問題
グリッド
最小カット
頂点に容量があるフロー
denseなグラフをスーパーノードでsparseにする
グラフの考えるべき辺数を減らす
最小コスト
黄色diff
見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある... 問題へのリンク 問題概要 の二次元グリッドが与えられる。各マスは 'S' のマス:カエルがいる 'T' のマス:カエルがそこにいきたい 'o' のマス:葉っぱがある '.' …
フロー大好き!!!!!!!! 問題へのリンク 問題概要 頂点 辺の DAG が与えられる。頂点 からスタートして頂点 へと向かいたい。すべての頂点 に対し、 から へと向かうパスと、 から へと向かうパスが存在することが保証されている。 頂点のうちいくつか…