1640 天气晴朗的魔法
程序员文章站
2022-07-14 19:29:04
...
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int MAXN = 2e5 + 7;
pair<int, pair<int, int> > e[MAXN];
int father[MAXN];
int n, m;
int find(int x){
return x == father[x] ? x : father[x] = find(father[x]);
}
void init(){
for(int i = 1; i <= n; ++i)
father[i] = i;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 0; i < m; ++i)
cin >> e[i].second.first >> e[i].second.second >> e[i].first;
sort(e, e + m);
int len = 0, num = 0;
init();
for(int i = 0; i < m; ++i){
int a = e[i].second.first, b = e[i].second.second;
a = find(a), b = find(b);
if(a == b) continue;
father[a] = b;
num++, len = i;
if(num == n - 1) break;
}
for(int i = 0; i < m; ++i)
if(e[i].first == e[len].first) len = i; //查找最长一条边的最后一个,可以二分做
long long ans = 0;
init();
for(int i = len; i >= 0; --i){
int a = e[i].second.first, b = e[i].second.second;
a = find(a), b = find(b);
if(a == b) continue;
father[a] = b;
ans += e[i].first;
}
cout << ans << endl;
}
上一篇: 量化理解(Google量化白皮书)
下一篇: svg笔记