103646: [Atcoder]ABC364 G - Last Major City

Problem Statement

The Country of AtCoder consists of $N$ cities and $M$ roads connecting them, and one can travel between any two cities by traversing some roads. The cities are numbered from $1$ to $N$, and the roads are numbered from $1$ to $M$. Road $i$ connects cities $A_i$ and $B_i$ bidirectionally.

Due to increasing traffic in the country, some roads are planned to be expanded. Currently, no roads have been expanded, and the cost to expand road $i$ is $C_i$.

Since it is difficult to expand all roads at once, the plan is to first designate $K$ out of the $N$ cities as major cities and perform the minimum necessary expansion work so that one can travel between any two major cities using only expanded roads. It has already been decided that cities $1, 2, \dots, K-1$ will be major cities, but the last major city has not yet been decided.

For each $i=K, K+1, \dots, N$, answer the following question:

• If city $i$ is designated as the last major city, what is the minimum total cost of the expansion work required to ensure that one can travel between any two major cities using only expanded roads?

Constraints

• $2 \leq N \leq 4000$
• $N-1 \leq M \leq 8000$
• $2\leq K \leq \min(N,\,$$10$

问题陈述

AtCoder国由N个城市和M条连接它们的道路组成，人们可以通过穿越一些道路在任意两个城市之间旅行。 城市从1到N编号，道路从1到M编号。道路i双向连接城市A_i和B_i。

由于国内交通量的增加，一些道路计划进行扩建。 目前，没有道路已经扩建，扩建道路i的成本是C_i。

由于不可能一次性扩建所有道路，计划首先将N个城市中的K个城市指定为主要城市，并进行必要的最小扩建工作，以便人们可以使用仅扩建的道路在任意两个主要城市之间旅行。 已经决定城市1、2、…、K-1将成为主要城市，但最后一个主要城市尚未决定。

对于每个i=K、K+1、…、N，回答以下问题：

• 如果城市i被指定为最后一个主要城市，那么为了确保人们可以使用仅扩建的道路在任意两个主要城市之间旅行，所需的扩建工作的最小总成本是多少？

约束条件

• 2 ≤ N ≤ 4000
• N-1 ≤ M ≤ 8000
• 2 ≤ K ≤ min(N, 10