【Educational Codeforces Round 33 C】 Rumor
Codeforces round 33 Educational
2023-09-14 09:03:45 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
显然最后会形成多个集合,每个集合里面的人能够可以互相到达。 则维护并查集的时候,顺便维护一下每个集合里面的最小值就好。 最后答案就为∑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;
}
相关文章
- codeforces Soldier and Number Game(dp+素数筛选)
- 【Codeforces Round #694 (Div. 1) C】Strange Shuffle
- 1800*2【Codeforces Round #612 (Div. 1) A】Garland
- 【Codeforces 140A】New Year Table
- 【Codeforces Round #519 by Botan Investments A】 Elections
- 【Codeforces Round #519 by Botan Investments C】 Smallest Word
- 【Codeforces 639A】Bear and Displayed Friends
- 【CodeForces 353 A】Domino
- 【Educational Codeforces Round 36 D】 Almost Acyclic Graph
- 【Codeforces Round #452 (Div. 2) A】 Splitting in Teams
- 【Educational Codeforces Round 33 B】Beautiful Divisors
- 【Codeforces Round #442 (Div. 2) D】Olya and Energy Drinks
- 【20.23%】【codeforces 740A】Alyona and copybooks
- 【codeforces 785C】Anton and Fairy Tale
- 【Codeforces Round #435 (Div. 2) C】Mahmoud and Ehab and the xor
- 【Codeforces Round #434 (Div. 2) B】Which floor?
- 【Codeforces Round #431 (Div. 2) C】From Y to Y
- 【Codeforces Round #428 (Div. 2) B】Game of the Rows
- 【 Codeforces Round #425 (Div. 2) D】Misha, Grisha and Underground
- 【Codeforces Round #425 (Div. 2) A】Sasha and Sticks
- 【Codeforces Round #424 (Div. 2) C】Jury Marks
- 【Codeforces Round #421 (Div. 2) A】Mister B and Book Reading
- 【codeforces 156C】Cipher
- CodeForces 453A 概率题
- Codeforces Round #263
- Codeforces Round #261 (Div. 2) D 树状数组应用
- Codeforces Round #246 (Div. 2)
- Educational Codeforces Round 20 A. Maximal Binary Matrix