链接：https://vjudge.net/problem/ZOJ-1586

题意：

在星系cgb的w-503行星中，有一种名为QS的智能生物。QS通过网络相互通信。如果两个QS想要连接，他们需要购买两个网络适配器（每个QS一个）和一段网络电缆。请注意，一个网络适配器只能在单个连接中使用。（即，如果QS想要设置四个连接，则需要购买四个适配器）。在通信过程中，QS将其消息广播到它所连接的所有QS，接收消息的QS组将消息广播到它们所连接的所有QS，重复该过程直到所有QS都收到消息。

思路：

最小生成树，权值包括连线的权值加上两个端点的适配器价格。

代码：

#include <iostream>#include <memory.h>#include <string>#include <istream>#include <sstream>#include <vector>#include <stack>#include <algorithm>#include <map>#include <queue>#include <math.h>#include <cstdio>using namespace std;typedef long long LL;const int MAXM = 1000000+10;const int MAXN = 1000+10;struct Path{ int _l,_r; double _value; bool operator < (const Path & that)const{ return this->_value < that._value; }}path[MAXM];int Father[MAXN];int a[MAXN];int n;int Get_F(int x){ return Father[x] = (Father[x] == x) ? x : Get_F(Father[x]);}void Init(){ for (int i = 1;i <= n;i++) Father[i] = i;}int main(){ int t; scanf("%d",&t); while (t--) { scanf("%d",&n); Init(); for (int i = 1;i <= n;i++) scanf("%d",&a[i]); int pos = 0; for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) { int len; scanf("%d",&len); if (i != j) { path[++pos]._l = i; path[pos]._r = j; path[pos]._value = len + a[i] + a[j]; } } sort(path+1,path+1+pos); int sum = 0; for (int i = 1;i <= pos;i++) { int tl = Get_F(path[i]._l); int tr = Get_F(path[i]._r); if (tl != tr) { Father[tl] = tr; sum += path[i]._value; } } printf("%d\n",sum); } return 0;}