牛客寒假算法基础集训营4 G Applese 的毒气炸弹

链接：https://ac.nowcoder.com/acm/contest/330/G
来源：牛客网

众所周知，Applese 是个很强的选手，它的化学一定很好。

今天他又AK了一套题觉得很无聊，于是想做个毒气炸弹玩。

毒气炸弹需要 k 种不同类型元素构成，Applese一共有 n 瓶含有这些元素的试剂。

已知元素混合遵循 m 条规律，每一条规律都可以用 "x y c" 描述。

表示将第 x 瓶试剂混入第 y 瓶试剂或者把第 y 瓶试剂混入第 x 瓶试剂，需要消耗 c 的脑力。

特别地，除了这 m 条规律外，Applese 可以将任意两瓶相同元素的试剂混合，且不需要消耗脑力。

Applese 想要配出毒气炸弹，就需要使 S 中含有 1∼k

把元素当作节点，需要k种元素。涉及合并。然后最小生成树

复习：记录边权，排序，选k-1条边

find函数已经忘了。初始化fa数组为 -1

find(x) 如果 fa[x]==-1 说明x就是根

否则 return fa[x]=find(fa[x]) 也就是一直往上查找

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int kind[maxn],n,m,k,fa[maxn];

 struct Edge{

     int u,v,c;

 }edge[maxn];

 bool cmp(Edge a,Edge b) {

     return a.c<b.c;

 }

 int find(int x) {

     if(fa[x]==-) return x;

     else return fa[x]=find(fa[x]);

 }

 void Union(int x,int y) {

     int fx=find(x);

     int fy=find(y);

     fa[fx]=fy;

 }

 int main() {

     scanf("%d%d%d",&n,&m,&k);

     for(int i=;i<=n;i++) scanf("%d",&kind[i]);

     int id=;

     long long ans=;

     while(m--) {

         scanf("%d%d%d",&edge[id].u,&edge[id].v,&edge[id++].c);

     }

     memset(fa,-,sizeof(fa));

     sort(edge,edge+id,cmp);

     int num=;

     for(int i=;i<id;i++) {

         if(find(kind[edge[i].u])==find(kind[edge[i].v])) continue;

         Union(kind[edge[i].u],kind[edge[i].v]);

         ans+=edge[i].c;

         if(++num==k-) break;

     }

     if(num==k-) printf("%lld",ans);

     else printf("-1");

     return ;

 }

巴特西

牛客寒假算法基础集训营4 G Applese 的毒气炸弹

最新文章

热门文章