Forsaken喜欢独一无二的树 题解

最小生成树kruskal求法这里不多赘述，就是对边权排序之后，用并查集去连接集合，知道剩下一个集合结束。

那么我们知道，如果要生成最小生成树唯一？为什么不唯一？就是因为存在连接两个集合中存在多种边权相同的方法。

那么我们直接把这些边权相同的但是连接相同的两个集合的一些边，留下一条，其余删掉就是最终答案了。

#include<bits/stdc++.h>
using namespace std;
typedef long long int;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
struct edge{
	int a,b,w;
}e[N];
int n,m;
bool cmp(edge a,edge b){
	return a.w<b.w;
}
int p[N];
int find_set(int x){
	if(x!=p[x]) {
		p[x]=find_set(p[x]);
	}
	return p[x];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>e[i].a>>e[i].b>>e[i].w;
	}
	for(int i=1;i<=n;i++)p[i]=i;
	sort(e+1,e+1+m,cmp);
	int ans=0;
	for(int i=1;i<=m;){	
		int j;
		for(j=i;j<=m;j++){
			if(e[i].w==e[j].w){
				if(find_set(e[j].a)!=find_set(e[j].b))
					ans+=e[i].w;
			}
			else
				break;
		}
		for(;i<j;i++){
			int x=find_set(e[i].a),y=find_set(e[i].b);
			if(x!=y){
				p[x]=y;
				ans-=e[i].w;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}