Kruskal 最小生成树CSP-S

💡 核心思想

Kruskal 算法按边权从小到大排序，依次选取不构成环的边加入生成树。判断是否构成环用并查集：如果边的两个端点不在同一集合则可以选。适合稀疏图，代码简洁。

🎯 直觉理解

想象你要修路连接所有村庄。你先把所有可能的路按造价排序，从最便宜的开始修。如果修这条路不会形成环路（即两端村庄还没被连通），就修。否则跳过看下一条。最后所有村庄都连通时，总造价最小。

📝 算法流程

1. 所有边按权值排序
2. 初始化并查集
3. 依次取边：若两端不在同一集合则合并，加入 MST
4. 选满 n-1 条边停止

$$\text{Kruskal 总复杂度：} O(E \log E) \text{（排序为主）}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
struct Edge { int u, v, w; };
bool operator<(const Edge& a, const Edge& b) { return a.w < b.w; }
int fa[5005];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
    int n, m; cin >> n >> m;
    vector<Edge> edges(m);
    for (auto& e : edges) cin >> e.u >> e.v >> e.w;
    sort(edges.begin(), edges.end());
    iota(fa, fa + n + 1, 0);
    long long total = 0, cnt = 0;
    for (auto& e : edges) {
        int pu = find(e.u), pv = find(e.v);
        if (pu != pv) { fa[pu] = pv; total += e.w; cnt++; }
        if (cnt == n - 1) break;
    }
    if (cnt < n - 1) cout << "orz" << endl;
    else cout << total << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目