比赛 |
20160923 |
评测结果 |
AAAAAAAAAA |
题目名称 |
口袋的天空 |
最终得分 |
100 |
用户昵称 |
Shirry |
运行时间 |
0.033 s |
代码语言 |
C++ |
内存使用 |
0.43 MiB |
提交时间 |
2016-09-23 22:49:12 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
using namespace std;
int N,M,K,u[10005]={0},v[10005]={0},w[10005]={0},r[10005]={0},F[10005]={0};
void Make_set(){
for(int i=1;i<=N;i++)F[i]=i;
}
bool cmp(int a,int b){
return w[a]<w[b];
}
int Findfather(int a){
if(F[a]==a)return F[a];
F[a]=Findfather(F[a]);
return F[a];
}
int main(){
freopen("cotton.in","r",stdin);
freopen("cotton.out","w",stdout);
int ans=0,p=0;
scanf("%d%d%d",&N,&M,&K);
int X,Y,L;
Make_set();
for(int i=1;i<=M;i++){
scanf("%d%d%d",&X,&Y,&L);
u[i]=X;
v[i]=Y;
w[i]=L;
r[i]=i;
}
sort(r+1,r+1+M,cmp);
for(int i=1;i<=M;i++){
int e=r[i];
int x=Findfather(u[e]);
int y=Findfather(v[e]);
if(x!=y){
ans+=w[e];
F[y]=x;
p++;
if(p==N-K)break;
}
}
if(p==N-K)printf("%d",ans);
else printf("No Answer");
return 0;
}