問題 問題概要 グラフはi - i+1 と i - i+2 を結ぶ２つ辺が貼られている。 二重連結グラフの状態を保ったまま辺を取り除き、辺のコストを最小にしたときの辺のコストの合計を求める。 解法 biconnected graph(2重連結グラフ)とは、任意の頂点を1つ取り除いて…

問題 問題概要 グラフが与えられる。そのグラフの中に三角形を作る。最小でいくつの辺を加えればできるか。 解法 まず、辺が1つもなければ、必要な最小の辺の数は3となる。次に辺がある場合を考える。u - v の辺がある場合を考える。このとき、u - x(xはvで…