読者です 読者をやめる 読者になる 読者になる

ACM-ICPC 2014 アジア地区東京大会 F

ACM-ICPC 2014 アジア地区東京大会 

F: There is No Alternative

問題
重み付き連結無向グラフが与えられる。
任意の最小全域木に含まれる辺の数とそれらの重みの和を求めよ。
頂点数N<=500
辺数M<=5000
重みC[i]、整数、1<=C[i]<=10000

解法
重み均一の時はグラフの橋判定により橋を列挙すれば良い(橋:取り除くと連結成分が増える辺)。
重みがある場合はクラスカル法をしながら橋判定をする。

重みWの辺については重みW以下の辺だけでグラフを作り、
重みWの辺が橋であるならばその辺は最小全域木に必須な辺である。
Wを1から10000まで試せば良い。

Codeforces #111 Div 2 D. Edges in MSP (http://codeforces.com/contest/160/problem/D)の下位互換になる。