Kruskal算法 42分 求助

P3366 【模板】最小生成树

oval_m @ 2022-01-25 17:16:39

看着书上码的

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll unsigned long long
using namespace std;
int va[5005], vb[5005];
ll w[200005];
int r[200005]; //排序后的w序号 边的
int p[5005];   //并查集        点的
int vexnum, arcnum;
bool cmp(const int a, const int b) { return w[a] < w[b]; }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } //在查找的同时更新p数组
int main()
{
    ios::sync_with_stdio(false);
    cin >> vexnum >> arcnum;
    memset(w, -1, sizeof(w)); //w初始化为ULLONG_MAX   18446744073709551615
    int a, b;
    ll ww;
    for (int i = 0; i < arcnum; i++) //直接读入
    {
        cin >> va[i] >> vb[i] >> w[i];
    }
    for (int i = 0; i < vexnum; i++)
        p[i] = i; //p[x]为节点x的父节点  没有父节点p[x]=x
    for (int i = 0; i < arcnum; i++)
        r[i] = i;
    sort(r, r + arcnum, cmp); //将权值小的边排前面 采用间接排序
    ll ans = 0;
    for (int i = 0; i < arcnum; i++)
    {
        int x, y;
        int temp = r[i];
        x = find(va[temp]);
        y = find(vb[temp]);
        if (x != y)
        {
            p[x] = y;
            ans += w[temp];
        }
    }
    cout << ans;
}

by Cerisier @ 2022-01-25 20:41:32

我的问题 /dk


by 「 」 @ 2022-01-26 20:52:20

@oval_m 所以我说,你数组开小了,你为什么不信啊。


by oval_m @ 2022-01-29 01:56:07

@「 」 果然! 感谢


上一页 |