看到数据范围5000就知道是prim,但比kruskal少44分QWQ

P3366 【模板】最小生成树

shuhao @ 2024-08-07 10:25:36

prim:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5000;
int n, m, x, y, z, res;
int e[N+10][N+10], d[N+10];
bool vis[N+10];

ll prim() {
    memset(vis, false, sizeof(vis));
    memset(d, 0x3f3f3f3f, sizeof(d));
    d[1] = 0;
    ll sum = 0;
    for(int i = 1; i <= n; i++) {
        int u = -1;
        for(int v = 1; v <= n; v++) {
            if(vis[v] == false && (u == -1 || d[v] < d[u])) u = v;
        }
        vis[u] = true;
        sum += d[u];
        for(int v = 1; v <= n; v++) {
            if(vis[v] == false) d[v] = min(d[v], e[u][v]);
        }
    }
    return sum;
}

int main() {
    cin >> n >> m;
    memset(e, 0x3f3f3f3f, sizeof(e));
    for(int i = 1; i <= m; i++) {
        cin >> x >> y >> z;
        e[x][y] = z; e[y][x] = z;
    }
    res = prim();
    if(res == 1061109568) cout << "orz";
    else cout << res;

    return 0;
}

kruskal:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5000;
int n, m;
ll res, cnt;
struct Edge {
    int u, v, w;
    bool operator < (Edge o) {
        return w < o.w;
    }
} e[N+10];
int fa[N+10];

void init() {
    cnt = n;
    for(int i = 1; i <= n; i++) fa[i] = i;
}

int find(int u) {
    if(fa[u] == u) return u;
    return fa[u] = find(fa[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if(u == v) return;
    fa[u] = v;
    cnt--;
}

ll kruskal() {
    sort(e+1, e+m+1);
    init();
    ll sum = 0;
    for(int i = 1; i <= m; i++) {
        int &u = e[i].u, &v = e[i].v;
        if(find(u) == find(v)) continue;
        merge(u, v);
        sum += e[i].w;
    }
    return (cnt == 1 ? sum : -1);
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    res = kruskal();
    if(res == -1) cout << "orz";
    else cout << res;

    return 0;
}

怎么办?


|