并查集MLE求助 每个点都是125MB
查看原帖
并查集MLE求助 每个点都是125MB
364847
_Kouki_楼主2022/1/28 11:22
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct node
{
	int x,y,v;
}way[10001];
int p[1001];
bool cmp(node a,node b)
{
	return a.v<b.v;
}
int find(int x)
{
	if(p[x]!=x) p[x]=find(x);
	return p[x];
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>way[i].x>>way[i].y>>way[i].v;
	}
	sort(way+1,way+m+1,cmp);
	int ans=0,sum=0;
	for(int i=1;i<=m;i++)
	{
		int fx=find(way[i].x),fy=find(way[i].y);
		if(fx!=fy)
		{
			p[fx]=fy;
			sum++;
			ans+=way[i].v;
		}
		if(sum==n-k)
		{
			cout<<ans;
			return 0; 
		}
	}
	cout<<"No Answer";
} 
2022/1/28 11:22
加载中...