洛谷P1195题：最小生成树与Kruskal算法实践

想象你面前有N朵独立的云彩，每朵云都可以通过特定代价与其他云相连。你的任务是将这些云连成K个"棉花糖"（即K个连通分量），每个棉花糖至少包含一朵云，且总连接代价最小。这与经典的图论问题——最小生成树(MST)非常相似，但有一个关键区别：我们不需要将所有节点连成一棵树，而是需要形成K棵树（称为最小生成森林）。

一、算法选择

Kruskal算法特别适合解决这个问题，因为：

1. 它按照边权从小到大处理，确保每次选择的都是当前最小的可用边

2. 使用并查集(Union-Find)数据结构高效管理连通性

3. 可以灵活控制连通分量的数量

二、完整代码

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

// 定义边的结构体
struct Edge {
    int x, y, l; // x和y表示云朵编号，l表示连接代价
    bool operator<(const Edge& other) const {
        return l < other.l; // 按代价从小到大排序
    }
};

vector<Edge> edges; // 存储所有边
vector<int> parent; // 并查集数组

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

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    
    // 初始化并查集
    parent.resize(N+1);
    for (int i = 1; i <= N; ++i) {
        parent[i] = i;
    }
    
    // 读取所有边
    edges.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].x >> edges[i].y >> edges[i].l;
    }
    
    // 按边权从小到大排序
    sort(edges.begin(), edges.end());
    
    int totalCost = 0;
    int connectedComponents = N; // 初始时每个云朵自成一个连通分量
    
    // Kruskal算法构建最小生成森林
    for (const auto& e : edges) {
        if (connectedComponents <= K) break; // 已经形成K个连通分量
        
        int rootX = find(e.x);
        int rootY = find(e.y);
        
        if (rootX != rootY) { // 如果不在同一个连通分量
            parent[rootY] = rootX; // 合并
            totalCost += e.l;
            connectedComponents--; // 连通分量减少1
        }
    }
    
    // 检查是否能形成K个棉花糖
    if (connectedComponents == K) {
        cout << totalCost << endl;
    } else {
        cout << "No Answer" << endl;
    }
    
    return 0;
}

三、代码详解

1. 数据结构准备

• 使用结构体Edge存储每条边的信息

• parent数组用于并查集操作

• edges向量存储所有输入的边

2. 并查集初始化

• 初始时每个云朵自成一个连通分量

• find函数实现了路径压缩，提高查询效率

3. 核心算法流程

• 将边按权值排序

• 依次处理每条边，合并不同连通分量

• 当连通分量数等于K时停止

• 累计连接代价

4. 结果验证

• 检查最终连通分量数是否恰好为K

• 输出总代价或"No Answer"

四、常见错误与调试技巧

1. 连通分量计数错误

• 初始值应为N（每个节点独立）

• 每次成功合并后减1

2. 边界条件处理

• 当K>N时直接输出"No Answer"

• 当K=1时退化为标准MST问题

3. 性能优化

• 输入规模较大时使用快速IO

• 确保并查集实现高效（路径压缩）