문제
정점이 n개이고 간선이 m개인, 가중치 있는 무방향 그래프 G가 있다. 각 간선은 1부터 m까지의 번호가 붙어 있다.
Gi를 그래프 G에서 i번째 간선만 없앤 그래프라고 하자.
여러분은 모든 i에 대해, 그래프 Gi에서 minimum spanning tree의 간선 가중치 총합을 구해야 한다.
입력
그래프는 다음과 같은 형식으로 주어진다.
n m
a<1> b1 w1
...
am bm wm
제한은 다음과 같다.
2 ≤ n ≤ 100,000, 1 ≤ m ≤ 200,000, 1 ≤ ai ≤ n, 1 ≤ bi ≤ n, 0 ≤ wi ≤ 1,000,000
그래프 G는 ai와 bi를 잇는 가중치 wi인 간선들로 구성된다. 입력으로 주어지는 그래프는 단순 그래프라는 것이 보장된다:
임의의 정점 쌍에 대해 두 정점을 연결하는 간선은 최대 하나이며, 모든 i에 대해 ai ≠ bi 임이 보장된다.
출력
m개의 줄에, i번째 줄에는 Gi의 minimum spanning tree의 가중치 총합을 출력한다.
만약 spanning tree가 없다면 -1을 출력한다.
예제 #1
4 6
1 2 2
1 3 6
1 4 3
2 3 1
2 4 4
3 4 5
8
6
7
10
6
6
예제 #2
4 4
1 2 1
1 3 10
2 3 100
3 4 1000
1110
1101
1011
-1
예제 #3
7 10
1 2 1
1 3 2
2 3 3
2 4 4
2 5 5
3 6 6
3 7 7
4 5 8
5 6 9
6 7 10
27
26
25
29
28
28
28
25
25
25
예제 #4
3 1
1 3 999
-1
출처
Japan Alumni Group Spring Contest 2013
로그인해야 코드를 작성할 수 있어요.