グラフ
問題 atcoder.jp 解法 の値が大きい方から小さい方に辺を張ると考えても良いので、そう考える。 となるような i, j, k を考え、頂点kからiかjのどちらかに辺を引くことを考える。 i-j 間のコストは j-k 間のコストは i-k 間のコストは の場合、 だから だか…
問題 atcoder.jp 解法 頂点 v から v+1 へ、長さ 0 の辺と、長さ の辺を張る。これによって、 の長さのパスが存在することになる。次に、頂点を の順番で見ていく。頂点 0 から頂点 v へは の長さのパスが存在するので、頂点 v から頂点 n-1 へ長さ t の辺を…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2893 解法 橋を全列挙し、それぞれについて削除したときの cost を求め、ソートすれば良い。具体的な実装としては、 橋を列挙する。 橋を含まない連結な部分グラフを潰して 1 つの頂点とし、…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2891 解法 N 頂点 N 辺のグラフ(いわゆる「なもりグラフ」)は1つだけ閉路があり、その閉路に木がいくつか連結している形になる。各クエリの頂点の両方とも閉路に含まれている場合2本切断す…
lowlink や橋や関節点について、いくつか問題を解いたのでリンクを貼っておく。 lowlink の説明 kagamiz.hatenablog.comkagamiz 先生による有名記事。大変わかりやすい。 関節点・橋の確認用問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=…
問題 https://beta.atcoder.jp/contests/arc039/tasks/arc039_d 解法 橋を2回通らずに A->B->C の移動が出来るかという問題になる。まず橋を検出し、それらを取り除くと、グラフはいくつかの連結成分に分かれる。各連結成分内では頂点間を移動する経路が常に…