社区讨论

90分,一个WA,并查集,求助!

P1111修复公路参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo2aeqae
此快照首次捕获于
2023/10/23 10:37
2 年前
此快照最后确认于
2023/11/03 10:48
2 年前
查看原帖
C
#include <bits/stdc++.h>
using namespace std;
int N,M,ans,min1=10000000;
int fa[100000];
struct aa{
	int a,b,t;
}s[100000];
int cmp(const aa &a,const aa &b){return a.t<b.t;}
void init()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++)
	    fa[i]=i;
	ans=N;
}
int find_root(int x)
{
	int r=x;	
	while(fa[r]!=r)
		r=fa[r];
    return r;
}
void join(int a,int b)
{
	int roota=find_root(a);
	int rootb=find_root(b);
	if(roota!=rootb)
	{
		fa[rootb]=roota;
		ans--;
	}
}
int main()
{
	init();
	for(int i=0;i<M;i++)
		cin>>s[i].a>>s[i].b>>s[i].t;
		sort(s+1,s+M+1,cmp);
	for(int i=1;i<=M;i++)	
	{
		join(s[i].a,s[i].b);
		if(ans==1)
		{
			cout<<s[i].t;
			return 0;
		}
	}	
	cout<<"-1";
	return 0;
}


哪里错了啊

回复

2 条回复,欢迎继续交流。

正在加载回复...