链接：https://ac.nowcoder.com/acm/contest/330/G
来源：牛客网
今天他又AK了一套题觉得很无聊，于是想做个毒气炸弹玩。
毒气炸弹需要 k 种不同类型元素构成，Applese一共有 n 瓶含有这些元素的试剂。
已知元素混合遵循 m 条规律，每一条规律都可以用 "x y c" 描述。
表示将第 x 瓶试剂混入第 y 瓶试剂或者把第 y 瓶试剂混入第 x 瓶试剂，需要消耗 c 的脑力。
Applese 想要配出毒气炸弹，就需要使 S 中含有 1∼k
把元素当作节点，需要k种元素。涉及合并。然后最小生成树
复习：记录边权，排序，选k-1条边
find函数已经忘了。 初始化fa数组 为 -1
find(x) 如果 fa[x]==-1 说明x就是根
否则 return fa[x]=find(fa[x]) 也就是一直往上查找
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=100010; 4 int kind[maxn],n,m,k,fa[maxn]; 5 6 struct Edge{ 7 int u,v,c; 8 }edge[maxn]; 9 10 bool cmp(Edge a,Edge b) { 11 return a.c<b.c; 12 } 13 14 int find(int x) { 15 if(fa[x]==-1) return x; 16 else return fa[x]=find(fa[x]); 17 } 18 19 void Union(int x,int y) { 20 int fx=find(x); 21 int fy=find(y); 22 fa[fx]=fy; 23 } 24 25 int main() { 26 scanf("%d%d%d",&n,&m,&k); 27 for(int i=1;i<=n;i++) scanf("%d",&kind[i]); 28 int id=0; 29 long long ans=0; 30 while(m--) { 31 scanf("%d%d%d",&edge[id].u,&edge[id].v,&edge[id++].c); 32 } 33 memset(fa,-1,sizeof(fa)); 34 sort(edge,edge+id,cmp); 35 int num=0; 36 for(int i=0;i<id;i++) { 37 if(find(kind[edge[i].u])==find(kind[edge[i].v])) continue; 38 Union(kind[edge[i].u],kind[edge[i].v]); 39 ans+=edge[i].c; 40 if(++num==k-1) break; 41 } 42 if(num==k-1) printf("%lld",ans); 43 else printf("-1"); 44 return 0; 45 }
原文：https://www.cnblogs.com/ACMerszl/p/10336005.html