【求助】用的kruskal,样例过了,但是10分
查看原帖
【求助】用的kruskal,样例过了,但是10分
757326
KanaAqua_qwq楼主2024/7/19 10:45
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,w,ans,uset[1000005],maxx=-1;
struct Edge{
	int u,v,w;
}edge[1000005];
bool cmp(Edge a,Edge b){
	return a.w<b.w;
}
int find(int x){
	if(x!=uset[x])uset[x]=find(uset[x]);
	return uset[x];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		edge[i].u=u,edge[i].v=v,edge[i].w=w;
	}
	for(int i=1;i<=n;i++)uset[i]=i;
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++){
		maxx=edge[i].w;
		if(find(edge[i].u)!=find(edge[i].v))edge[i].u=find(edge[i].v);
		ans++;
		if(ans==n-1)break;
	}
	cout<<ans<<" "<<maxx<<endl;
	return 0;
}
2024/7/19 10:45
加载中...