kruskalRE4个点求解
查看原帖
kruskalRE4个点求解
579506
Respects_H楼主2022/7/24 22:12
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define AM 100000000
#define MOD 8011200
int n,m,t[AM];
struct Edge{
	int u,v,w;
	bool operator<(const Edge& b) const{
		return w<=b.w;
	}
};
std::vector<Edge> edges;
void add(int u,int v,int w){
	edges.push_back({u,v,w});
}
int f[AM],cnt;
void init(int x){
	for(int i=1;i<=x;i++)
		f[i]=i;
}
int find(int x){
	return (f[x]==x?x:f[x]=find(f[x]));
}
void merge(int x,int y){
	f[find(x)]=find(y);
}
bool judge(int x,int y){
	return find(x)==find(y);
}
int id[AM],od[AM];
int kruskal(){
	int res=0;
	std::sort(edges.begin(),edges.end());
	for(Edge e:edges){
		if(!judge(e.u,e.v)){
			merge(e.u,e.v);
			cnt++;
			res+=e.w;
			
		}
	}
	return res;
}
int main(){
	scanf("%d %d",&n,&m);
	init(n);
	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
	}
	int ans=kruskal();
	if(cnt==n-1)
		printf("%d",ans);
	else
		printf("orz");
	return 0;
}
2022/7/24 22:12
加载中...