56分kruskal求助
查看原帖
56分kruskal求助
613082
qscisQJing楼主2022/4/14 11:45

实测是sort那一行炸了,RE

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
int n,m,ans,cnt;int fa[MAXN];
struct edge
{
	int u,v,w;
}ed[200005];
bool cmp(edge x,edge y){return x.w<=y.w;}
int find(int x)
{
	if(x!=fa[x])fa[x]=find(fa[x]);
	return fa[x];
}
void work()
{
	sort(ed,ed+m,cmp);
	for(int i=0;i<m;i++)
	{
		
		int fau=find(ed[i].u),fav=find(ed[i].v);
		if(fau==fav)
			continue;
		ans+=ed[i].w;
		fa[fau]=fav;
		if(++cnt==n-1)break;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)fa[i]=i;
	for(int i=0;i<m;i++)
		cin>>ed[i].u>>ed[i].v>>ed[i].w;
	//	for(int i=0;i<m;i++)cout<<link[i].w;
	work();
	cout<<ans;
	return 0;
}
2022/4/14 11:45
加载中...