比赛 20160923 评测结果 EEEEEEEEEE
题目名称 口袋的天空 最终得分 0
用户昵称 KZNS 运行时间 1.534 s
代码语言 C++ 内存使用 0.45 MiB
提交时间 2016-09-23 19:25:27
显示代码纯文本
//KZNS
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 1003
#define Mmax 10003
int pa[Mmax], pb[Mmax];
int v[Mmax];
int ls[Mmax];
int fa[Nmax];
int N, M, K;
inline bool cmp(const int &a, const int &b) {
    return v[a] < v[b];
}
void rin() {
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 0; i < M; i++)
        scanf("%d %d %d", pa+i, pb+i, v+i);
}
void fir() {
    for (int i = 1; i <= N; i++)
        fa[i] = i;
    for (int i = 0; i < M; i++)
        ls[i] = i;
    sort(ls, ls+M);
}
int FA(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = FA(x);
}
void work() {
    int ks = N;
    int cst = 0;
    int a, b;
    int t;
    for (int i = 0; i < M; i++) {
        t = ls[i];
        a = pa[t];
        b = pb[t];
        if (FA(a) != FA(b)) {
            ks--;
            cst += v[t];
            fa[fa[a]] = fa[b];
        }
        if (ks == K)
            break;
    }
    if (ks == K)
        printf("%d\n", cst);
    else
        printf("No Answer\n");
}
int main() {
    freopen("cotton.in", "r", stdin);
    freopen("cotton.out", "w", stdout);
    rin();
    fir();
    work();
    return 0;
}
//UBWH