denseなグラフをスーパーノードでsparseにする
おおむね BFS だけど、ちょっとだけ TLE に注意。。。 問題へのリンク 問題概要 のグリッドが与えられる。"." は通路マス、"#" は壁で侵入不能マス、"S" はスタート、"G" はゴールである。さらに英小文字で表された各マス間は 1 手で自由にワープで行き来可…
Codeforces
グラフ問題
二部グラフ
最小全域木
Kruskal法
色に関する問題
クリーク
denseなグラフをスーパーノードでsparseにする
操作
最小コスト
制約:複数系列の長さの合計が10^5以下
条件の言い換え
必要条件を列挙したら十分条件になる
補集合を考える
CodeforcesOthers
CodeforcesR2400
カラフルにする
種類数
むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、…
AtCoder
AtCoder500点
ABC-E
グラフ問題
DP
最短路問題
二値パラメータ問題
ほとんどのところで値が一定値に決まる
小さいところで帳尻を合わせる
Dijkstra法
グラフの頂点を倍加する
denseなグラフをスーパーノードでsparseにする
各kに対して
青色diff
2回やる意味はない
これ、頂点を倍加してダイクストラする系。 問題へのリンク 問題概要 頂点 辺の連結な無向グラフが与えられる。各辺 には 通行に要する料金 円 (所持金が 以上でなければ通行できない) 通行に要する所要時間 秒 という属性がある。また、各頂点 では所持金を…
AtCoder
AtCoder800点
ARC-F
フロー
グラフ問題
グリッド
最小カット
頂点に容量があるフロー
denseなグラフをスーパーノードでsparseにする
グラフの考えるべき辺数を減らす
最小コスト
黄色diff
見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある... 問題へのリンク 問題概要 の二次元グリッドが与えられる。各マスは 'S' のマス:カエルがいる 'T' のマス:カエルがそこにいきたい 'o' のマス:葉っぱがある '.' …