欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1640 天气晴朗的魔法

程序员文章站 2022-07-14 19:29:04
...

1640 天气晴朗的魔法



#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;
}

相关标签: 生成树