比赛 |
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;
}