最小生成树

一、Kruskal 算法

核心：克鲁斯卡尔算法是一种用于求解加权连通图的最小生成树的算法。其基本思想是按照边的权值从小到大的顺序选择边，并保证所选的边不构成回路，直到选出 n-1 条边为止。

• 边权从小到大：排序、贪心
• 不构成回路/环：并查集

例题：

修复公路_牛客题霸_牛客网

这道题要求我们找到一个最小的时间，使得所有城市构成一个连通图。问题的核心在于，如果我们能在时间  达成目标，那么在任何大于  的时间点，目标也一定是达成的。这暗示了我们可以通过某种方式寻找这个关键的“瓶颈”时间点。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef pair<long, long> pll;
const int mod = 1e7;
const int N = 1e3 + 5;
const int M = 1e5 + 5;int fa[N];int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);
}struct Rode
{int u, v, t;
}a[M];void solve(){int n, m;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> a[i].u >> a[i].v >> a[i].t;}for(int i = 1; i <= n; ++i) fa[i] = i;//初始化每个节点的父亲都是其自身sort(a + 1, a + 1 + m, [&](Rode r1, Rode s2)->bool{return r1.t < s2.t;});//按照边权排序int ans = -1;int cnt = 0;for(int i = 1; i <= m; ++i){int ra = find(a[i].u);int rb = find(a[i].v);if(ra != rb){//若u和v的父亲不一样，则说明不在一个集合里，那么进行合并,若相同，则说明已经在一个集合里了，再加入会构成回环fa[ra] = rb;ans = a[i].t;cnt++;}}//判断是否形成最小生成树，若不等于n-1，说明形成森林（多棵树）if(cnt == n - 1) cout << ans;else cout << -1;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin >> T;while(T--){solve();}return 0;
}