糖果
from https://ac.nowcoder.com/acm/contest/9983/G
时间限制：2s
空间限制：26MB
题目描述：
在一个幼儿园里面有n个小朋友，分别编号1,2,…,n。在这些小朋友中有一些小朋友互为朋友关系，总共有m对朋友。
作为幼儿园老师，你想买一些糖果分给小朋友，你知道第i个小朋友想要至少ai个糖果，否则他就会不开心。
同时，如果一个小朋友得到的糖果数小于他某个朋友得到的糖果数，他也会不开心。
请问你最少买多少糖果才能保证每个小朋友都不会不开心呢？
输入格式：
第一行以空格分隔的两个整数n,m。
第二行以空格分隔的n个正整数ai。
接下来m行每行以空格分隔的两个正整数u,v，代表u是v的朋友，v是u的朋友。
1≤n≤106
0≤m≤106
1≤ai≤109
1≤u,v≤n,u≠v
输出格式：
购买的最少糖果数以保证每个小朋友都不会不开心。
输入样例：
3 1
1 2 3
1 2
输出样例：
7
并查集，有朋友关系的（间接或直接），都放入到同一个集合，在分配糖果的时候，给集合中的每一个人都分配该集合中需要糖果最多的人的个数（一个人需要1个，一个人需要2个，那么给他们都分配2个，这样才能满足两个人都不生气）。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int father[1000005]; //存储祖先节点索引
int maxn[1000005]; //存储该集合每个人所需最大糖果数
int from,to,x,y; //from和to代表有朋友关系的两个人，x和y代表他们在树当中的祖先节点
int n,m; //人数和关系数
long long sum = 0; //统计需要糖果个数
int find(int x){ //查找父亲if(x == father[x])return x;return father[x] = find(father[x]);
}
int main(){scanf("%d %d",&n,&m);for(int i = 1;i <= n;++i)scanf("%d",maxn + i),father[i] = i; //输入每个人需要的糖果数，并且将每个人的祖先定为自己for(int i = 1;i <= m;++i){ //合并有朋友关系的人scanf("%d %d",&from,&to);x = find(from),y = find(to);if(x != y)father[x] = y;maxn[y] = max(maxn[y],maxn[x]);}for(int i = 1;i <= n;++i)sum += maxn[find(i)]; //累加每个人所需最小糖果数printf("%lld",sum);return 0;
}
