链接：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;}
ZOJ-1586-QS Network
原文地址：https://www.cnblogs.com/YDDDD/p/10331571.html