比赛 防止浮躁的小练习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;
}