Luogu P3366 Code

这道题有2种解法，分别是 \(Kruskal\) 算法 和 \(Prim\) 算法

\(Kruskal\) 算法

实现方法：从小到大遍历每一条线，如果该线连接的两点已经都在树内则不处理，否则描出这条线

使用并查集维护该树

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

pair<int, pair<int, int>> g[N];  // The weight on the line between Point A and Point B, Point A, Point B

int fa[N];  // Father Point

int f(int x) {  // Finding Point X's Extra Grandpa
    if (fa[x] == x) return x;
    return fa[x] = f(fa[x]);
}

int main() {
    int m, n;
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++)  // Saving
        cin >> u >> v >> w,
        g[i].first = w,
        g[i].second.first = u,
        g[i].second.second = v;
    for (int i = 1; i <= n; i++) fa[i] = i;  // Initialize All Points' Father as themselves
    sort(g + 1, g + m + 1);
    int ans = 0, cnt = 0;  // Use cnt to make sure that all point was connected
    for (int i = 1; i <= m; i++) {
        int u = g[i].second.first, v = g[i].second.second, w = g[i].first;  // Reading
        if (f(u) == f(v)) continue;  // Had been connected
        ans += w, fa[f(v)] = fa[u], cnt++;  // Add the weight, connect Point V and Point U
    }
    if (cnt == n - 1) cout << ans << endl;  // If there's n points, then there will be connecting for n - 1 times
    else cout << "orz" << endl;  // Some points didn't connected
    return 0;
}

\(Prim\) 算法

本人不会 待更新