C10第4章 最小生成树

admin

Prim 算法
3 3
1 2 19
2 3 11
3 1 7

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
    int v, next;
    int len;
} E[MAX_M];
int p[MAX_N], eid;
bool used[MAX_N];
void init() {
    memset(p, -1, sizeof(p));
    memset(used, false, sizeof(used));
    eid = 0;
}
void insert(int u, int v, int len) {
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}
int prim(int n) {
    int sum = 0;
    int dist[MAX_N];
    memset(dist, 0x3f, sizeof(dist));
    memset(used, false, sizeof(used));
    dist[1] = 0;
    for (int i = 0; i < n; ++i) {
        int min_v = -1, min_d = 0x3f3f3f3f;
        for (int j = 1; j <= n; ++j) {
            if (!used[j] && dist[j] < min_d) {
                min_d = dist[j];
                min_v = j;
            }
        }
        sum += min_d;
        used[min_v] = true;
        for (int i = p[min_v]; i != -1; i = E[i].next) {
            int v = E[i].v;
            dist[v] = min(dist[v], E[i].len);
        }
    }
    return sum;
}

int main() {
    int n, m;
    cin >> n >> m;
    init();
    for (int i = 0; i < m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        insert(u, v, len);
        insert(v, u, len);
    }
    cout << prim(n) << endl;
    return 0;
}