代码

P1195 口袋的天空 (NOIP Kruskal复习)

[infobox title="https://www.luogu.org/problem/show?pid=1195"]题目背景

小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖。

题目描述

给你云朵的个数N,再给你M个关系,表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成K个棉花糖,一个棉花糖最少要用掉一朵云,小杉想知道他怎么连,花费的代价最小。[/infobox]

解法...
没有解法..直接把最后K个结果忽略就好了...

#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 5050
#define MAXM 200050
using namespace std;
struct edge{
    int x, y, d;
}e[MAXM];
int f[MAXN];
int n, m, k;

int find(int i){
    if (i != f[i]) f[i] = find(f[i]);
    return f[i];
}

bool cmp(edge a, edge b){
    return a.d < b.d;
}

int main(){
    int ans = 0;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].d);
    for (int i = 0; i < n; i++) f[i] = i;
    sort(e, e + m, cmp);
    int cnt = 0;
    for (int i = 0; i < m; i++){
        int af = find(e[i].x), bf = find(e[i].y);
        if (af != bf){
            f[bf] = af;
            ans += e[i].d;
            cnt++;
            if (cnt == n - k) break;
        }
    }
    printf("%d", ans);
}

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐