本文主要是介绍Rumor并查集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Rumor
原题链接https://vjudge.net/contest/350427#problem/E
带权并查集的一点应用,将每个位置的权值记录,使用权值最小的来作为根,这里的权值跟其他的没有关系,所以不需要变化,每个集合都为最小值为根,根所需要的钱就是这个集合传播到所有人所需要的钱,再判断有多少个集合,将所有的根的钱加起来即为答案。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
long long pre[300005];
long long re[300005];
long long find(long long x)
{if (x == pre[x]){return x;}return pre[x] = find(pre[x]);
}
void join(long long x, long long y)
{long long ss1 = find(x);long long ss2 = find(y);if (ss1 != ss2){if (re[ss1] < re[ss2])//比较权值大小,较小的为根{pre[ss2] = ss1;}else{pre[ss1] = ss2;}}
}
int main()
{long long i, n, m;scanf("%lld %lld", &n, &m);for (i = 1; i <= n; i++){scanf("%lld", &re[i]);pre[i] = i;}while (m--){long long sum1, sum2;scanf("%lld %lld", &sum1, &sum2);join(sum1, sum2);}long long sum = 0;for (i = 1; i <= n; i++){if (pre[i] == i)//找到所有的根{sum += re[i];}}printf("%lld", sum);return 0;
}
这篇关于Rumor并查集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!