Prim

liyuan2023 · 2025-03-23 14:14:24 · 算法·理论

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005, inf = 1e9;
struct Edge {
    int v, w;
};
vector<Edge> g[maxn];
int n, m, ans, cost[maxn];
bool vis[maxn];
bool prim() {
    fill(cost+2, cost+n+1, inf); // cost[1] = 0
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || cost[j] < cost[u]))
                u = j;
        if (cost[u] == inf)
            return false;
        ans += cost[u];
        vis[u] = true;
        for (auto e : g[u]) {
            int v = e.v, w = e.w;
            cost[v] = min(cost[v], w);
        }
    }
    return true;
}
int main() {
    cin >> n >> m;
    for (int i = 0, u, v, w; i < m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w}); 
    }
    if (!prim()) cout << "orz" << endl;
    else cout << ans << endl;
    return 0;
}