机房里有 n 个人，每个人一台电脑，从 1 到 n 编号。 由于一些不可告人的原因，这 n 个人需要用一种特殊的网线连起来，有 m 种选择网线的方法，每条网线形如 (x,y,z) 表示架设 x 和 y 之间的网线需要 z 元。 作为机房管理员，你需要使得机房里每个人都能通过网线直接或者间接与其他所有人相连，钱自然是由管理员出。 当然，对于架设的结果，如果与 x 直接相连的有 p 人，与 y 直接相连的有 q 人，且 p>q ，那么看起来 x 与其他人进行网络沟通会更加方便，这样有失公平。 所以经过协商，每个人给出了一个 a[i] ，如果与第i个人直接相连的人有 b[i] 个，那么第i个人愿意支付 a[i]*b[i] 的钱给管理员。 求使得机房每个人都相连的情况下，管理员需要用的最少的钱。
第一行两个整数 n ， m 第二行 n 个整数表示 a[1] 到 a[n] 接下来 m 行每行三个整数 x ， y ， z 描述一条可以架设的网线 n≤ 10^5 m≤ 2*10^5 a[i]≤ 100 200≤ z≤ 10^9
一行，一个整数表示答案
4 4 5 5 6 7 1 2 200 1 3 200 1 4 200 3 4 200
565
考点：图
数据规模 n ≤ 1e5 ｜ 限制 2 秒 / 256MB ｜ 标准输入输出
推荐方向：图
本题切入点
先求最小生成树保证连通，再按每条边的度数代价 a[x]·b[x] 综合选边——把收益折进边权做 MST。
把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。
思路框架（图 通法 · 非本题专属）
实现要点：注意是有向图还是无向图，无向图加边记得双向。
复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)
该范式的通法易错点
对照本题
样例 1：输入 4 4 / 5 5 6 7 / 1 2 200 / 1 3 200 / 1 4 200 / 3 4 200 → 输出 565
这里选择第1，第3，第4条网线，网线架设共用去600元，与第1个到第4个人直接相连的有2,1,1,2个人，ta们会支付给管理员10+5+6+14=35元，随意最后总最小支出为565元。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：【2023】贝壳找房春招Java工程师笔试卷1；【2023】贝壳找房春招C++工程师笔试卷1；【2023】贝壳找房春招测试开发工程师笔试卷1。