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