比赛 防止颓废的小练习v0.3 评测结果 AAAAAAAAAA
题目名称 口袋的天空 最终得分 100
用户昵称 农场主 运行时间 0.040 s
代码语言 C++ 内存使用 0.28 MiB
提交时间 2016-10-19 09:57:00
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define maxn 1001
using namespace std;
class edge{
public:
	int from,to,dis;
	bool operator < (const edge e)const{
		return dis<e.dis;
	}
};
vector<edge> edges;
int f[maxn]={0};
int n,m,k;
void init(){
	for (int i=1;i<=n;i++) f[i]=i;
}
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
void read(){
	int u,v,w;
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		edges.push_back((edge){u,v,w});
	}
	sort(edges.begin(),edges.end());
	int tot=n,i=0,ans=0;
	init();
	while(tot>k&&i!=edges.size()){
		edge e=edges[i++];
		u=find(e.from); v=find(e.to);
		if (u==v) continue;
		else{
			f[u]=v;
			tot--;
			ans+=e.dis;
		}
	}
	if (tot!=k) printf("No Answer\n");
	else printf("%d",ans);
}
int main(){
	freopen("cotton.in","r",stdin);
	freopen("cotton.out","w",stdout);
	read();
}