最小生成树（MST问题）
（稀疏图）Prim算法
使用邻接矩阵存图，以 \(\mathcal{O}(N^2+M)\) 的复杂度计算，思想与 \(\tt djikstra\) 基本一致。
const int N = 550, INF = 0x3f3f3f3f;
int n, m, g[N][N];
int d[N], v[N];
int prim() {ms(d, 0x3f); //这里的d表示到“最小生成树集合”的距离int ans = 0;for (int i = 0; i < n; ++ i) { //遍历 n 轮int t = -1;for (int j = 1; j <= n; ++ j)if (v[j] == 0 && (t == -1 || d[j] < d[t])) //如果这个点不在集合内且当前距离集合最近t = j;v[t] = 1; //将t加入“最小生成树集合”if (i && d[t] == INF) return INF; //如果发现不连通，直接返回if (i) ans += d[t];for (int j = 1; j <= n; ++ j) d[j] = min(d[j], g[t][j]); //用t更新其他点到集合的距离}return ans;
}
int main() {ms(g, 0x3f); cin >> n >> m;while (m -- ) {int x, y, w; cin >> x >> y >> w;g[x][y] = g[y][x] = min(g[x][y], w);}int t = prim();if (t == INF) cout << "impossible" << endl;else cout << t << endl;
} //22.03.19已测试
（稠密图）Kruskal算法
平均时间复杂度为 \(\mathcal{O}(M\log M)\) ，简化了并查集。
struct DSU {vector<int> fa;DSU(int n) : fa(n + 1) {iota(fa.begin(), fa.end(), 0);}int get(int x) {while (x != fa[x]) {x = fa[x] = fa[fa[x]];}return x;}bool merge(int x, int y) { // 设x是y的祖先x = get(x), y = get(y);if (x == y) return false;fa[y] = x;return true;}bool same(int x, int y) {return get(x) == get(y);}
};
struct Tree {using TII = tuple<int, int, int>;int n;priority_queue<TII, vector<TII>, greater<TII>> ver;Tree(int n) {this->n = n;}void add(int x, int y, int w) {ver.emplace(w, x, y); // 注意顺序}int kruskal() {DSU dsu(n);int ans = 0, cnt = 0;while (ver.size()) {auto [w, x, y] = ver.top();ver.pop();if (dsu.same(x, y)) continue;dsu.merge(x, y);ans += w;cnt++;}assert(cnt < n - 1); // 输入有误，建树失败return ans;}
};