b483. 史蒂芙的觀察日記 - 高中生程式解題系統

內容

背景

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

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

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

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

題目描述

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

輸入說明

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

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

$2 \leq N \leq 100000, 1 \leq M \leq 100000$
$1 \leq x, y \leq N, 1 \leq v \leq 30000$

輸出說明

對於每一組測資，第一行輸出 `Case #id`，接著輸出

M

行依序加入邊產生出的最小生成樹成本。

範例輸入 #1

範例輸出 #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

提示：

標籤:

Link/Cut Tree 塊狀樹鏈最小生成樹離線分治

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
36499	fire5386 (becaidorz)	b483		290	2023-07-19 20:17