7-6 ysu-情报
Brotherhood在燕大建立了分部，但由于燕大人杰地灵，不是什么人都能够任意进出的，于是现在一个棘手的问题摆在了Ezio面前：情报的传递。
已知燕大内的Brotherhood一共有n个团体，有些团体之间有一些关系，你可以把它们看作一条边，每条边连接了两个不同的团体，现在一共有m条边。
现在前辈Jumbo要求Ezio将一个情报传递给燕大内的所有团体。已知Ezio亲自去向团体i告知情报的代价为val[i]。Ezio当然不想一个一个去找啦，他还有很多任务要完成，于是他发现他可以利用团体之间的关系，让某一个已经被传达过情报的团体去告知另一与之有关系团体。
但是团体内部的人懒癌发作，自然不想白白地去帮Ezio跑腿。具体来说，针对关系(u,v)，如果Ezio想要利用它，应该付出的代价为cost(u,v)。
现在Ezio想要花费最少的代价，你能帮帮他吗？
注意：输入包括多组测试用例。
第一行一个整数t，表示测试用例组数。
对于每组测试用例：
第一行两个用空格隔开的整数n和m，分别表示团体个数和关系数量。
接下来一行n个用空格隔开的数，第i个数表示val[i]。
接下来m行，每行三个用空格隔开的整数u,v和cost(u,v)。
对于每组测试用例，你的程序需要输出一行一个整数表示询问的答案。
在这里给出一组输入。例如：
2 5 8 2 8 5 1 10 1 2 5 1 3 9 3 4 5 2 5 6 3 2 2 1 3 8 5 3 4 4 1 8 5 8 7 2 9 10 3 1 2 8 1 3 6 1 4 4 2 5 3 4 5 2 2 4 9 3 5 3 5 4 2在这里给出相应的输出。例如：
14 14第一组测试用例中，Ezio可以直接将情报传递给1,4号团体，花费分别为2,1。
然后利用关系(4,3),(3,5),(3,2)，花费分别为5,4,2。
/*本题可以ac 经验结论，利用并查集求最小生成树的时候最好弄个有向图 不仅节省空间 还和无向图结果一样 */ #include<bits/stdc++.h> using namespace std; const int N=2e5+100; struct edge{ int u,v,w; }edge[N]; int f[N]; int t,n,m; int find(int x) { if(x!=f[x]) { f[x]=find(f[x]); } return f[x]; } bool cmp(struct edge x,struct edge y) { return x.w<y.w; } int main() { cin>>t; while(t--) { long long res=0; cin>>n>>m; for(int i=1;i<=n+1;i++) { f[i]=i; } int k=0; for(int i=1;i<=n;i++) { int a; cin>>a; edge[k].u=i; edge[k].v=n+1; edge[k].w=a; k++; /* edge[k].u=n+1; edge[k].v=i; edge[k].w=a; k++; */ } for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; edge[k].u=a,edge[k].v=b,edge[k].w=c; k++; /* edge[k].u=b,edge[k].v=a,edge[k].w=c; k++; */ // /*a=find[a]; b=find[b]; if(a!=b) { f[a]=b; } */ } sort(edge,edge+k,cmp); for(int i=0;i<k;i++) { int a=edge[i].u; int b=edge[i].v; a=find(a); b=find(b); if(a!=b) { f[a]=b; res+=edge[i].w; } } cout<<res<<endl; } }
