【Educational Codeforces Round 33 C】 Rumor

在这里输入题意

【题解】

显然最后会形成多个集合,每个集合里面的人能够可以互相到达。
则维护并查集的时候,顺便维护一下每个集合里面的最小值就好。
最后答案就为∑min{每个集合}

【代码】

/*

  	1.Shoud it use long long ?

  	2.Have you ever test several sample(at least therr) yourself?

  	3.Can you promise that the solution is right? At least,the main ideal

  	4.use the puts("") or putchar() or printf and such things?

  	5.init the used array or any value?

  	6.use error MAX_VALUE?

  	7.use scanf instead of cin/cout?

*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

int f[N+10],mi[N+10],n,m;

bool bo[N+10];

int ff(int x){

	if (f[x]==x) return x;

	else return f[x] = ff(f[x]);

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("F:\\c++source\\rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

	cin >> n >> m;

	for (int i = 1;i <= n;i++){

		cin >> mi[i];

		f[i] = i;

	}

	for (int i = 1;i <= m;i++){

	 	int x,y;

	 	cin >> x >> y;

	    int r1 = ff(x),r2 = ff(y);

	    if (r1!=r2){

	     	f[r1] = r2;

	     	mi[r2] = min(mi[r2],mi[r1]);

		}

	}

	long long ans = 0;

	for (int i = 1;i <= n;i++){

	 	int x = ff(i);

	 	if (!bo[x]){

	 	 	bo[x] = true;

	 	 	ans += mi[x];

	 	}

	}

	cout << ans << endl;

	return 0;

}

巴特西

【Educational Codeforces Round 33 C】 Rumor

最新文章

热门文章