比赛 20160923 评测结果 AAAAAAAAAA
题目名称 口袋的天空 最终得分 100
用户昵称 iortheir 运行时间 0.042 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2016-09-23 19:26:54
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define pb push_back

const int maxn=10000+100;

int n;
int m;
int k;

int father[maxn];

int x;
int y;
int l;
int ans=0;

class T
{
	public:
		int u;
		int v;
		int w;
};

vector<T>A;

inline int cmp(const T &a,const T &b)
{
	return a.w<b.w;
}

inline int find(int x)
{
	if(x==father[x])
	{
		return x;
	}
	else
	{
		father[x]=find(father[x]);
		return father[x];
	}
}

inline void unionn(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	father[fx]=fy;
}

int main()
{
	freopen("cotton.in","r",stdin);
	freopen("cotton.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<maxn;++i)
	{
		father[i]=i;
	}
	for(int i=0;i<m;++i)
	{
		scanf("%d%d%d",&x,&y,&l);
		A.pb((T){x,y,l});
	}
	if(k==n)
	{
		cout<<0;
	}
	if(k>n)
	{
		cout<<"No Answer";
		return 0;
	}
	int kount=0;
	sort(A.begin(),A.end(),cmp);
	for(int i=0;i<m;++i)
	{
		if(find(A[i].v)!=find(A[i].u))
		{
			unionn(A[i].u,A[i].v);
			ans+=A[i].w;
			kount++;
			if(n-kount==k)
			{
				break;
			}
		}
	}
	if(n-kount==k)
	{
		cout<<ans;
	}
	else
	{
		cout<<"No Answer";
	}
	return 0;
}