srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

二重連結グラフ

SRM 693 div2 medium BiconnectedDiv2

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