問題
n개의 노드와 m개의 간선을 갖는 무방향 그래프 G가 주어진다.
각 간선들은 1에서 m까지 번호가 매겨져 있다.
그래프 G에서 k번째 간선을 지운 그래프를 Gk 라고 할 때,
모든 k에 대하여 Gk에서 만들어지는 최소비용신장트리의 비용을 계산하는 프로그램을 작성하시오.
入力
입력데이터 형식은 아래와 같다.
n m a1 b1 w1 … am bm wm
첫 행에 n과 m이 공백으로 구분되어 주어진다. n( 2≤ n ≤ 100,000)과 m( 1 ≤ m ≤ 200.000)은 각각 노드 수와 간선 수를 나타낸다. 다음 행부터 m행에 걸쳐 간선의 정보 ak( 1≤ ak ≤n), bk( 1 ≤ bk ≤ n), wk( 0 ≤ wk ≤ 1,000,000)가 공백으로 구분되어 주어지며, 이는 노드 ak와 노드 bk사이에 비용이 wk임을 의미한다. ak ≠ bk 이고 임의의 노드사이에 간선은 많아야 한 개이다.
出力
m행에 걸쳐 각 k에 대하여 k번째 간선을 지운 그래프 Gk에서 만들어지는 최소비용신장트리의 비용을 출력하시오.
Gk에서 최소비용신장트리가 존재하지 않는 경우 -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
タグ
ログインしないとコードを書けません。