比赛 |
防止颓废的小练习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();
}