比赛 |
防止浮躁的小练习V0.1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
口袋的天空 |
最终得分 |
100 |
用户昵称 |
AntiLeaf |
运行时间 |
0.013 s |
代码语言 |
C++ |
内存使用 |
0.41 MiB |
提交时间 |
2016-10-07 16:34:12 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010,maxm=10010;
struct edge{
int from,to,dis;
bool operator<(const edge &e)const{return dis<e.dis;}
}e[maxm];
int Kruskal();
int findroot(int);
void mergeset(int,int);
int prt[maxn],n,m,k,ans=0;
int main(){
#define MINE
#ifdef MINE
freopen("cotton.in","r",stdin);
freopen("cotton.out","w",stdout);
#endif
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].dis);
ans=Kruskal();
if(ans==-1)printf("No Answer");
else printf("%d",ans);
#ifndef MINE
printf("\n--------------------DONE--------------------\n");
for(;;);
#endif
return 0;
}
int Kruskal(){
int cnt=0,ans=0,x,y;
for(int i=1;i<=n;i++)prt[i]=i;
sort(e+1,e+m+1);
for(int i=1;cnt!=n-k&&i<=m;i++){
x=e[i].from;
y=e[i].to;
if(findroot(x)==findroot(y))continue;
cnt++;
ans+=e[i].dis;
mergeset(x,y);
}
return cnt==n-k?ans:-1;
}
int findroot(int x){
return prt[x]==x?x:(prt[x]=findroot(prt[x]));
}
void mergeset(int x,int y){
x=findroot(x);
y=findroot(y);
if(x!=y)prt[x]=y;
}