比赛 |
防止浮躁的小练习V0.1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
口袋的天空 |
最终得分 |
100 |
用户昵称 |
NVIDIA |
运行时间 |
0.034 s |
代码语言 |
C++ |
内存使用 |
0.47 MiB |
提交时间 |
2016-10-07 18:24:32 |
显示代码纯文本
#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;
}