提出 #33481914

---

ソースコード 拡げる

N,M = gets.split.map(&:to_i)
ABC = $<.map{|ln| ln.split.map(&:to_i) }

E = Array.new(N+1){[]}
G = [-1]*(N+1)
F = lambda{|a|
	G[a]<0 ? a : G[a] = F[G[a]]
}
U = lambda{|a,b,c|
	x,y = F[a],F[b]
	next 0 if x==y
	x,y = y,x if G[y]<G[x]
	G[x] += G[y]
	G[y] = x
	E[a]<<[b,c]
	E[b]<<[a,c]
	next c
}
S = ABC.sort_by{_3}.sum{|a,b,c,| U[a,b,c] }

P = [nil]*(N+1)
D = [nil]*(N+1)
C1 = [nil]*(N+1)
P[0] = D[0] = C1[0] =
P[1] = D[1] = C1[1] = 0
*Q = 1
while a = Q.pop
	d = D[a]+1
	E[a].each{|b,c|
		next if D[b]
		P[b] = a
		D[b] = d
		C1[b] = c
		Q<<b
	}
end

AC = [(as,cs = P,C1)]
up = true
while up
	up = false
	AC<<(as,cs = (N+1).times.map{|i|
		a,c = as[i],cs[i]
		up |= as[a]!=a
		next as[a],[cs[a],c].max
	}.transpose)
end

C = lambda{|a,b|
	da,db = D[a],D[b]
	a,b,da,db = b,a,db,da if db<da
	c,dd = C1[b],db-da
	AC.each_with_index{|(as,cs),i|
		b,c = as[b],[c,cs[b]].max if 0<dd[i]
	}
	next c if a==b
	AC.reverse_each{|as,cs|
		a,b,c = as[a],as[b],[c,cs[a],cs[b]].max if as[a]!=as[b]
	}
	next [c,C1[a],C1[b]].max
}

puts ABC.map{|a,b,c| S-C[a,b]+c }

提出情報

ジャッジ結果