Prim中可以不用dis数组?

P3366 【模板】最小生成树

DiDi123 @ 2022-04-11 22:32:42

事实证明,Prim中 d 数组似乎没啥用……

下面的程序好像也能过

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
struct edge {
    int to, w, nex;
} Edge[MAXN << 2];
int head[5005], tot, sum, cnt, vis[5005], n, m;
void add(int u, int v, int w) {
    Edge[cnt].nex = head[u];
    Edge[cnt].to = v;
    Edge[cnt].w = w;
    head[u] = cnt++;
}
struct node {
    int pos, dis;
    bool operator < (const node &x) const {
        return dis > x.dis;
    }
};
priority_queue <node> q;
void prim() {
    node temp;
    temp.dis = 0, temp.pos = 1;
    q.push(temp);
    while (!q.empty() && tot < n) {
        int u = q.top().pos, w = q.top().dis;
        q.pop();
        if (vis[u]) continue;
        tot++, sum += w;
        vis[u] = 1;
        for (int i = head[u]; i != -1; i = Edge[i].nex) {
            temp.dis = Edge[i].w, temp.pos = Edge[i].to;
            q.push(temp);
        }
    }
}
int main() {
    memset(head, -1, sizeof(head));
    int a1, a2, a3;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a1 >> a2 >> a3;
        add(a1, a2, a3);
        add(a2, a1, a3);
    }
    prim();
    if (tot == n) cout << sum;
    else cout << "orz";
}

by 蕾姆莉雅 @ 2022-04-13 22:53:54

%%%困扰了我好久的dis数组orz


by L1ngYu @ 2022-04-29 23:14:42

枚举下一个要走的点然后统计权值和就行。不需要更新 \operatorname{dist} 数组


|