HELP!!!!
查看原帖
HELP!!!!
352963
sehunnnn1楼主2020/10/20 20:50
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,k,sum,t;
const int N=1e4+12;
int dad[N];
struct node
{
	int u,v,q;
}f[N];
bool cmp(node x,node y)
{
	return x.q<y.q;
}
int find(int x){
	if(x==dad[x]) return x;
	else return dad[x]=find(x);
}

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) dad[i]=i;
	for(int i=1;i<=m;i++)
		cin>>f[i].u>>f[i].v>>f[i].q;
	sort(f+1,f+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int a1=find(f[i].u),a2=find(f[i].v);
		if(a1==a2) continue;
		else
		{
			t++;dad[a1]=find(dad[a2]);
			sum+=f[i].q;
		}
		if(t==n-k)
		{
			cout<<sum;
			return 0;
		}
	}
	cout<<"No Answer";
	return 0;
}
2020/10/20 20:50
加载中...