A/B's Blog

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

代码 b-a -

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

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

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

题目描述

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

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

解法…
没有解法..直接把最后K个结果忽略就好了…
[code lang=”cpp”]#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);
}[/code]

版权所有 © 呆毛 2018 ⁄ 主题 INN AO