A - Rumor
题目描述
Vova 对自己发誓，绝不再玩电脑游戏…… 但最近，知名的游戏开发商暴火娱乐有限公司，发布了他们的最新游戏 “World of Farcraft”，并且该游戏变得非常流行。显然，Vova 又开始玩这款游戏。
现在，他尝试解决一个任务。这项任务是，来到一个名叫 Overcity 的定居点，并在里面散播谣言。
Vova 知道，在 Overcity 有 n 个人物角色。某些人物角色互为朋友，他们共享所获得的信息。Vova 也知道，他可以给每个人物角色好处，以便人物角色开始散播谣言；第 i 个人物角色想要 ci 的黄金，作为散播谣言的交换。当一个人物角色听到了谣言之后，他就告诉自己的所有朋友，他的朋友们也开始散播谣言给自己的朋友 (免费)，依此类推。
当全部的 n 个人物角色都听到了谣言时，任务完成。请问，Vova 至少需要多少黄金，才能完成这项任务？
如果你对题意仍有疑问，请参见样例说明。
输入格式
第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105)，分别表示 Overcity 的人物角色数量，以及存在多少对的朋友关系。
第二行包含 n 个整数 ci (0 ≤ ci ≤ 109) 表示第 i 个人物角色需要的黄金，以便开始散播谣言。
接下来的m 行，每行包含两个数 (xi, yi)，表示人物角色 xi 和 yi 是朋友关系 (1 ≤ xi, yi ≤ n, xi ≠ yi)。数据保证，每对朋友最多被列出一次。
输出格式
打印一个数，表示 Vova 为了完成任务所必须花费的最少黄金。
输入输出样例
输入
5 2
2 5 3 4 8
1 4
4 5
输出
10
输入
10 0
1 2 3 4 5 6 7 8 9 10
输出
55
输入
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
输出
15
样例说明
在第一个样例中，最优决策是给第 1 个人物角色好处 (他将会散播谣言给第 4 个人物角色，并且第 4 个人物角色会散播谣言给第 5 个人物角色)。同时，Vova 还必须给第 2 个、第 3 个人物角色，分别给予好处，以便他们得知谣言。
在第二个样例中，Vova 必须给每个人好处。
在第三个样例中，最优决策是给第 1 个、第 3 个、第 5 个、第 7 个、第 9 个人物角色，分别予以好处。
ac代码：
/* author : Linux_sky*/
#include <iostream>
#include <algorithm>
using namespace std;
int par[100010];
int Rank[100010];
int cost[100010];
int n,m,a,b;
int find(int x)
{
if(par[x] == x) return x;
else return par[x] = find(par[x]);//路径压缩
}
void unite(int x,int y)
{
x = find(x); y = find(y);
if(x == y) return ;
if(Rank[x] < Rank[y]) par[x] = y;
else
{
par[y] = x;
if(Rank[x] == Rank[y]) Rank[x]++;
}
}
bool same(int x,int y)
{
return find(x)==find(y);
}
void init()
{
int i = 0;
for(i = 1;i<=n;i++)
{
par[i] = i;
Rank[i] = 0;
}
return ;
}
int main()
{
scanf("%d %d",&n,&m);
int i = 0;
for(i = 1;i<=n;i++) scanf("%d",&cost[i]);
init();
for(i = 0;i<m;i++)
{
scanf("%d %d",&a,&b);
unite(a,b);
//par[b] = find(a);//压缩路径
}
/* printf("%d : %d\n",i,par[i]); */
/* } */
for(i = 1;i<=n;i++) cost[find(i)] = min(cost[find(i)],cost[i]);
long long ans = 0;
for(i = 1;i<=n;i++)
{
/* printf("%d : %d\n",i,cost[i]); */
if(par[i] == i) ans += cost[i] ;
}
printf("%lld\n",ans);
return 0;
}