机房里有个人，每个人一台电脑，从到编号。由于一些不可告人的原因，这个人需要用一种特殊的网线连起来，有种选择网线的方法，每条网线形如表示架设和之间的网线需要元。作为机房管理员，你需要使得机房里每个人都能通过网线直接或者间接与其他所有人相连，钱自然是由管理员出。当然，对于架设的结果，如果与直接相连的有人，与直接相连的有人，且，那么看起来与其他人进行网络沟通会更加方便，这样有失公平。所以经过协商，每个人给出了一个，如果与第i个人直接相连的人有个，那么第i个人愿意支付的钱给管理员。求使得机房每个人都相连的情况下，管理员需要用的最少的钱。

问答题

机房里有 $\mathit n\$ 个人，每个人一台电脑，从 $\text 1\$ 到 $\mathit n\$ 编号。

由于一些不可告人的原因，这 $\mathit n\$ 个人需要用一种特殊的网线连起来，有 $\mathit m\$ 种选择网线的方法，每条网线形如 $\text (x,y,z)\$ 表示架设 $\mathit x\$ 和 $\mathit y\$ 之间的网线需要 $\mathit z\$ 元。

作为机房管理员，你需要使得机房里每个人都能通过网线直接或者间接与其他所有人相连，钱自然是由管理员出。

当然，对于架设的结果，如果与 $\mathit x\$ 直接相连的有 $\mathit p\$ 人，与 $\mathit y\$ 直接相连的有 $\mathit q\$ 人，且 $\mathit p>q\$ ，那么看起来 $\mathit x\$ 与其他人进行网络沟通会更加方便，这样有失公平。

所以经过协商，每个人给出了一个 $\text a[i]\$ ，如果与第i个人直接相连的人有 $\text b[i]\$ 个，那么第i个人愿意支付 $\text a[i]*b[i]\$ 的钱给管理员。

求使得机房每个人都相连的情况下，管理员需要用的最少的钱。

查看答案

上一题

下一题

题目信息

校招真题

正确率

点击

我的笔记