《P1195 口袋的天空》

题目背景

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

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

题目描述

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

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

输入格式

第一行有三个数 N,M,K。

接下来 M 行每行三个数 X,Y,L，表示 X 云和 Y 云可以通过 L 的代价连在一起。

输出格式

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 K 个棉花糖，请输出 No Answer。

输入输出样例

输入 #1复制

3 1 2
1 2 1

输出 #1复制

1

说明/提示

对于 30% 的数据，1≤N≤100，1≤M≤103；

对于 100% 的数据，1≤N≤103，1≤M≤104，1≤K≤10，1≤X,Y≤N，0≤L<104。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 表示云朵之间的连接关系
struct Edge {
int x, y, l;
Edge(int x_, int y_, int l_) : x(x_), y(y_), l(l_) {}
// 用于排序，按代价从小到大
bool operator<(const Edge& other) const {
return l < other.l;
}
};

vector<int> parent;

// 查找根节点，带路径压缩
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}

// 合并两个集合
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false; // 已经在同一个集合中
parent[y] = x;
return true;
}

int main() {
int N, M, K;
cin >> N >> M >> K;

// 特殊情况：需要的棉花糖数量多于云朵数量
if (K > N) {
cout << "No Answer" << endl;
return 0;
}

vector<Edge> edges;
for (int i = 0; i < M; i++) {
int x, y, l;
cin >> x >> y >> l;
edges.push_back(Edge(x, y, l));
}

// 初始化并查集
parent.resize(N + 1); // 云朵编号从1开始
for (int i = 1; i <= N; i++) {
parent[i] = i;
}

// 按代价从小到大排序边
sort(edges.begin(), edges.end());

int totalCost = 0;
int components = N; // 初始时每个云朵都是一个独立的连通分量

// 使用传统for循环代替范围for循环
for (int i = 0; i < edges.size(); i++) {
if (components == K) break;
// 通过索引访问元素
if (unite(edges[i].x, edges[i].y)) {
totalCost += edges[i].l;
components--;
}
}

// 检查是否成功形成了K个连通分量
if (components == K) {
cout << totalCost << endl;
} else {
cout << "No Answer" << endl;
}

return 0;
}