b483: 史蒂芙的觀察日記
Tags : Link/Cut Tree 塊狀樹鏈 最小生成樹 離線分治
Accepted rate : 11人/13人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-10 18:19

Content

背景

史蒂芙在學院讀書時,教授曾經教過最小生成樹 (Minimum Spanning Tree,簡稱 MST),MST 最常見到的兩個算法 Kruskal's Algorithm、Prim's Algorithm,還有其他的算法來得到 MST。

在某一次作業中,史蒂芙被特別指派的某一道題目,題目描述「給定好一棵 MST,接著新增加一條邊,請問新的最小生成樹成本為何。」聰明的史蒂芙想到一個樸素的解法「增加新的一條邊若造成 MST 上存在一個環,只要把環上最權重最大的邊移除,最小生成樹就大功告成。」

萬萬沒想到,正高興地要拿著 $O(V)$ 算法交差時,卻沒想到一連串的詢問,於是史蒂芙被命令回去觀察觀察一番再交出報告。

「看來史蒂芙還是只有被欺負的份呢。」

題目描述

給定 $N$ 個點、$M$ 條雙向邊,依序給定每一條邊,每增加一條邊,輸出當前的最小生成樹成本,若圖不連通,則輸出最小生成森林成本。

Input

有多組測資,每一組測資第一行有兩個整數 $N, M$。

接下來會有 $M$ 行,每一行上會有三個整數 $x, \; y, \; v$,表示依序加入的無向邊,點 $x$ 連接到點 $y$ 成本為 $v$。節點編號為 $1 \cdots N$。

  • $2 \le N \le 100000, \; 1 \le M \le 100000$
  • $1 \le x, y \le N, \; 1 \le v \le 30000$
Output
對於每一組測資,第一行輸出 `Case #id`,接著輸出 $M$ 行依序加入邊產生出的最小生成樹成本。
Sample Input #1
3 3
1 2 1
1 3 2
2 3 4
5 7
1 2 9
2 3 8
3 4 7
4 5 6
2 4 5
1 4 4
2 5 3
Sample Output #1
Case #1
1
3
3
Case #2
9
17
24
30
27
22
19
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (5%): 2.0s , <10M
公開 測資點#6 (5%): 2.0s , <10M
Hint :
Tags:
Link/Cut Tree 塊狀樹鏈 最小生成樹 離線分治
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」