P13600 [NWRRC 2022] Computer Network

Cupa 正在使用 $n$ 台计算机和一个集线器搭建一个连通的网络。 这些计算机编号为 $1$ 到 $n$。每台计算机 $i$ 有一根输出线缆，可以在 $d_i$ 毫秒内将 1 位数据传输到另一端。 集线器有 $k$ 个端口，可以连接计算机的线缆，每台计算机只有一个端口。 Cupa 要求每台计算机的线缆必须连接到某个端口——可以是集线器的端口，也可以是另一台计算机的端口。同时，必须保证每台计算机都能将数据传输到集线器，无论是直接连接还是通过其他计算机中转。 每台计算机 $i$ 的网络延迟 $t_i$ 定义为从计算机 $i$ 向集线器发送 1 位数据所需的时间。假设中转的计算机将收到的数据立即通过自己的输出线缆转发，不需要额外时间。 网络搭建完成后，Cupa 会计算每台计算机的网络延迟 $t_i$。他希望所有计算机的总网络延迟 $t_1 + t_2 + \ldots + t_n$ 尽可能小。 请帮助 Cupa 设计网络连接方案，使总网络延迟最小。

第一行包含两个整数 $n$ 和 $k$，分别表示计算机数量和集线器的端口数量（$1 \leq k \leq n \leq 100$）。 第二行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$，表示每台计算机线缆的数据传输时间（$1 \leq d_i \leq 100$）。

输出一个整数，表示最小可能的总网络延迟。

在第一个样例中，Cupa 应该将第 2 台和第 3 台计算机连接到集线器，将第 1 台计算机连接到第 3 台计算机。此时 $t_1 = 20 + 10 = 30$，$t_2 = 30$，$t_3 = 10$。答案为 $t_1 + t_2 + t_3 = 70$。 在第二个样例中，所有计算机应按任意顺序串联成一条链，最终连接到集线器。总网络延迟为 $10 + 20 + 30 + 40 + 50 = 150$。 由 ChatGPT 4.1 翻译