AT_abc364_g [ABC364G] Last Major City

题目描述

AtCoder 国由 $N$ 个城市以及连接这些城市的 $M$ 条道路组成，任意两个城市之间都可以通过若干条道路互相到达。每个城市编号为 $1$ 到 $N$，每条道路编号为 $1$ 到 $M$，第 $i$ 条道路双向连接城市 $A_i$ 和 $B_i$。

由于 AtCoder 国的交通量逐年增加，计划对部分道路进行扩建。目前尚未有任何道路被扩建，扩建第 $i$ 条道路的花费为 $C_i$。

由于一次性扩建所有道路过于困难，首先会从 $N$ 个城市中指定 $K$ 个城市作为主要城市，并进行最少的扩建工程，使得所有主要城市之间仅通过已扩建的道路即可互相到达。城市 $1,2,\dots,K-1$ 已经确定为主要城市，最后一个主要城市尚未确定。

请对于 $i=K,K+1,\dots,N$，分别回答以下问题：

• 若将城市 $i$ 作为最后一个主要城市，最少需要多少扩建费用，才能使所有主要城市之间仅通过已扩建的道路互相到达？

输入格式

输入按以下格式从标准输入读入。

$N$ $M$ $K$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

输出 $N-K+1$ 行。第 $l$ 行（$1\leq l\leq N-K+1$）输出当 $i=l+K-1$ 时问题的答案，输出一个整数。

输入输出样例 #1

输入 #1

4 5 3
1 4 3
3 4 4
1 2 4
2 3 2
1 3 1

输出 #1

3
6

输入输出样例 #2

输入 #2

4 3 2
2 4 28
1 4 56
1 3 82

输出 #2

84
82
56

输入输出样例 #3

输入 #3

6 12 4
2 6 68
2 5 93
4 6 28
2 4 89
3 6 31
1 3 10
1 2 53
3 5 1
3 5 74
3 4 22
4 5 80
3 4 35

输出 #3

85
64
94

说明/提示

限制条件

• $2\leq N\leq 4000$
• $N-1\leq M\leq 8000$
• $2\leq K\leq \min(N,\,10)$
• $1\leq A_i < B_i \leq N$
• $1\leq C_i \leq 10^9$
• 任意两个城市之间都可以通过若干条道路互相到达
• 输入均为整数

样例解释 1

如上图，带数字的圆圈表示城市编号，带数字的线表示扩建该道路所需的费用。左右两图分别对应 $i=3,4$ 的情况，带颜色的圆圈为主要城市，带颜色的粗线为最优解中被扩建的道路。

• 当 $i=3$ 时，扩建道路 $4,5$，总费用为 $2+1=3$，这是最小值。
• 当 $i=4$ 时，扩建道路 $1,4,5$，总费用为 $3+2+1=6$，这是最小值。

样例解释 3

可能存在多条道路连接同一对城市的情况。

由 ChatGPT 4.1 翻译