链接:https://ac.nowcoder.com/acm/contest/9983/G
来源:牛客网
在一个幼儿园里面有n\mathit nn个小朋友,分别编号1,2,...,n\text 1,2,...,n1,2,...,n。在这些小朋友中有一些小朋友互为朋友关系,总共有m\mathit mm对朋友。
作为幼儿园老师,你想买一些糖果分给小朋友,你知道第i\mathit ii个小朋友想要至少aia_{i}ai个糖果,否则他就会不开心。
同时,如果一个小朋友得到的糖果数小于他某个朋友得到的糖果数,他也会不开心。
请问你最少买多少糖果才能保证每个小朋友都不会不开心呢?
一道并查集模板题,估计是给没学过并查集的人熟悉一下。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; int n,m; int a[maxn]; int father[maxn]; int num[maxn]; int findfather (int x) { int a=x;while (x!=father[x]) x=father[x]; while (a!=father[a]) { int z=a;a=father[a];father[z]=x; } return x; } void Union (int x,int y) { x=findfather(x); y=findfather(y); if (x==y) return; if (a[x]<=a[y]) { father[x]=y; num[y]+=num[x]; num[x]=0; } else { father[y]=x; num[x]+=num[y]; num[y]=0; } } int main () { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",a+i); for (int i=1;i<=n;i++) father[i]=i,num[i]=1; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); Union(x,y); } long long ans=0; for (int i=1;i<=n;i++) { if (findfather(i)==i) ans+=1ll*num[i]*a[i]; } printf("%lld\n",ans); }