E - QS Network
题目链接：
https://vjudge.net/contest/66965#problem/E
题目：
在星系cgb的w-503行星中，有一种名为QS的智能生物。 QS通过网络相互通信。如果两个QS想要连接，他们需要购买两个网络适配器（每个QS一个）和一段网络电缆。请注意，一个网络适配器只能在单个连接中使用。（即，如果QS想要设置四个连接，则需要购买四个适配器）。在通信过程中，QS将其消息广播到它所连接的所有QS，接收消息的QS组将消息广播到它们所连接的所有QS，重复该过程直到所有QS都收到消息。
示例如下所示：
QS网络示例，QS A想要发送消息。
步骤1. QS A向QS B和QS C发送消息;
步骤2. QS B向QS A发送消息; QS C向QS A和QS D发送消息;
步骤3.该过程终止，因为所有QS都收到了该消息。
每个QS都有其优质的网络适配器品牌，并始终在其所有连接中购买该品牌。 QS之间的距离也不同。考虑到每个QS优先品牌的网络适配器的价格以及每对QS之间的电缆价格，您的任务是编写一个程序来确定设置QS网络的最低成本。
输入
输入的第一行包含一个整数t，表示数据集的数量。
从第二行开始，有t个数据集。
在单个数据集中，第1行包含一个表示QS数的整数n。
第二行包含n个整数，表示每个QS最喜欢的网络适配器的价格。
在第3行到第n + 2行包含一个矩阵，表示ecah对QS之间的电缆价格。
限制：
输入中的所有整数都是非负数且不超过1000。
产量
对于每个数据集，输出一行中的最小成本。不需要额外的空行。
样本输入
1
3
10 20 30
0 100 200
100 0 300
200 300 0
样本输出
370
思路：这道题要处理的东西比模板多一点，就是每个QS都有自己喜欢的适配器价格，然而两人之间需要有电缆，电缆也因人而异，
所以以往的node[i].w+=x改成node[i].w+=x+a[i]+a[j]，就是两者之间的适配器加上i->j和j->i之间的电缆价格就行了，主意数组要开大
我用的2e5+10wa掉了，用的2e6+10就ac了
// // Created by hy on 2019/7/30. // #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> using namespace std; typedef long long ll; const int maxn=2e6+10; int father[maxn],a[maxn]; struct Node{ int u,v,w; bool operator<(const Node &other)const{ return this->w<other.w; } }node[maxn]; int find(int x) { if(x==father[x]) return x; return father[x]=find(father[x]); } int main() { int T; int n; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<=n;i++) father[i]=i; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } int p; int m=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&p); node[m].u=i; node[m].v=j; node[m++].w=p+a[i]+a[j]; } } int sum=0; int cnt=0; sort(node,node+m); for(int i=0;i<m;i++) { int uu=find(node[i].u); int vv=find(node[i].v); if(uu==vv) continue; else { sum+=node[i].w; father[uu]=vv; cnt++; if(cnt==n-1) break; } } printf("%d ",sum); } return 0; }