Kruskal 解法

题目描述

小杉坐在教室里，透过口袋一样的天空，看着口袋一样的云朵。他想把一些云朵连起来，做成棉花糖。
给你 $n$ 朵云，编号从 $1$ 到 $n$，再给你 $m$ 个可以连接云朵的关系，每个关系表示可以用一定的代价把两朵云连起来。
小杉想要用最少的代价，把所有云朵做成 恰好 $k$ 个棉花糖（一个棉花糖就是一团连在一起的云朵）。
如果无法做成恰好 $k$ 个棉花糖，请输出 No Answer。

解题思路

1. 问题转化：最小生成森林

这是一个经典的最小生成树（MST）变种问题，我们需要构建的是最小生成森林。

• 初始状态：每一朵云都是一个独立的连通分量，共有 $n$ 个分量。
• 目标状态：我们需要剩下 $k$ 个连通分量。
• 操作逻辑：每连接一条边，就会减少一个连通分量。因此，我们需要进行 $(n - k)$ 次成功的连接操作。

为了让总代价最小，我们应该优先选择代价最小的边来连接云朵。这正是 Kruskal（克鲁斯卡尔）算法 的核心思想。

2. Kruskal 算法的应用

Kruskal 算法的流程非常适合这个场景：

1. 排序：将所有边按照权值（代价）从小到大排序。
2. 贪心选择：利用**并查集（Disjoint Set Union, DSU）**数据结构，依次尝试连接每条边的两个端点。
   • 如果两个端点不在同一个连通分量中，则连接它们（合并集合），并累加代价。
   • 如果连通分量的数量减少到了 $k$，说明任务完成，直接结束。
3. 判定：如果遍历完所有边，连通分量的数量依然大于 $k$，说明无法完成任务。

算法分析

• 时间复杂度：主要耗时在边的排序上，为 $O(m \log m)$。
• 空间复杂度：$O(n + m)$，用于存储边集和并查集数组。

代码解释

1. 数据结构

• struct node：用来存储一条边的信息（起点 u，终点 v，代价 w）。
• operator< 重载：定义了边的排序规则是按 w 从小到大排，这样 sort 函数就能直接使用。

2. 并查集 (find 函数)

• 这是一个带路径压缩的 find 函数。
• 它能快速找到一个节点所在集合的“根”，并且在查找过程中扁平化树结构，使得后续查询更快。

3. Kruskal 逻辑 (kruskal 函数)

• 初始化：f[i] = i，让每个节点的父节点都是自己。
• 计数器 cnt：初始化为 $n$，表示当前有 $n$ 个独立的云朵。
• 核心循环：遍历每条边，如果能连接两个不同的集合，就合并它们，并让 cnt--。
• 终止条件：当 cnt == k 时，说明我们已经成功把云朵分成了 $k$ 块，立即返回 true。

代码实现

#include <bits/stdc++.h>

#define endl "\n"
#define N 200005
#define ll long long

using namespace std;

// 存储边的结构体
struct node
{
    int u, v, w; // 起点u，终点v，权值w
    // 重载小于号，用于按权值从小到大排序
    friend bool operator<(node a, node b)
    {
        return a.w < b.w;
    }
} e[N];

int n, m, k, f[N], ans; // f[]是并查集数组，ans存总代价

// 并查集查找函数（带路径压缩）
int find(int x)
{
    if (f[x] == x)
        return x;
    return f[x] = find(f[x]);
}

// Kruskal算法主逻辑
bool kruskal()
{
    // 1. 初始化并查集
    for (int i = 1; i <= n; i++)
        f[i] = i;
    
    int cnt = n; // cnt表示当前连通分量的数量，初始为n
    
    // 2. 遍历所有边（已经从小到大排好序了）
    for (int i = 1; i <= m; i++)
    {
        int r1 = find(e[i].u), r2 = find(e[i].v);
        
        // 如果两个点不在同一个集合中
        if (r1 != r2)
        {
            cnt--;              // 连通分量数量减1
            f[r2] = r1;         // 合并集合
            ans += e[i].w;      // 累加代价
            
            // 如果已经达到了目标：剩下k个连通分量
            if (cnt == k)
                return true;    // 返回成功
        }
    }
    // 如果边用完了还没达到k个分量，返回失败
    return false;
}

int main()
{
    // 读入数据
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    
    // 将边按权值从小到大排序
    sort(e + 1, e + 1 + m);
    
    // 执行Kruskal算法
    if (kruskal())
        printf("%d", ans); // 成功，输出最小总代价
    else
        printf("No Answer"); // 失败
    
    return 0;
}