比赛 20160923 评测结果 AAAAAAAAAA
题目名称 口袋的天空 最终得分 100
用户昵称 NVIDIA 运行时间 0.060 s
代码语言 C++ 内存使用 0.47 MiB
提交时间 2016-09-23 21:50:10
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int f[10005]={0},n,m,k,a,b,c,sum=0,t=0;
struct Edg 
{
	int u;
	int v;
	int w;
}e[10005];
int getf(int v)
{
	if(f[v]==v)return v;
	else return f[v]=getf(f[v]);
}
bool xar(const Edg &a,const Edg &b)//编译时必须要加const,蜜汁algorithm冲突 
{
	if(a.w<b.w)return 1;
	else return 0;
}
int main()
{
	
	freopen("cotton.in","r",stdin);
	freopen("cotton.out","w",stdout);
	cin>>n>>m>>k;
	if(m<n-k||n<k)
	{
		cout<<"No Answer";
		return 0;
	}
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		e[i].u=a;
		e[i].v=b;
		e[i].w=c;
	}
	sort(e+1,e+m+1,xar);
	int fx,fy;
	for(int i=1;i<=m;i++)
	{
		fx=getf(e[i].u);
		fy=getf(e[i].v);
		if(fx!=fy)
		{
			f[fx]=fy;
			sum+=e[i].w;
			t++;
		}
		if(t==n-k)break;
	}
	cout<<sum<<endl;
	
	return 0;
}