第一次写Prim算法, RE on #8~10, 悬关

P3366 【模板】最小生成树

Gcc_Gdb_7_8_1 @ 2024-08-22 19:04:15

/**
 * @file Prim.cpp
 * @brief 求出最小生成树
 * @details 给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。
 * @mainpage main函数读入点数和边数,然后读入每条边的信息,最后调用Prim函数使用Prim算法计算输出最小生成树的权值和,如果Prim返回-1(即图不连通),输出orz。
 * @author Gcc_Gdb_7_8_1
 * @version 1.0
 * @date 2024-8-22
 */

#include <cstdio>
#include <queue>
#include <cstring>

/// @brief 定义边结构体 (1 <= weight <= 10000)
struct Edge
{
    int from, to, weight, next;
    Edge() {}
    Edge(int f, int t, int w, int n): from(f), to(t), weight(w), next(n) {}
} edges[200010];

/// @brief tot: 当前边数, head: 每个点的第一条边, n: 点数(1 <= n <= 5000), m: 边数 (1 <= m <= 200000)
int tot, head[5010], n, m;

/// @brief 插入边到图中
/// @param u 起始点
/// @param v 终止点
/// @param w 边权值
void insert(int u, int v, int w)
{
    edges[++tot] = Edge(u, v, w, head[u]);
    head[u] = tot;
}

/// @brief 标记数组和距离数组
bool vis[5010];
int dis[5010];

/// @brief 为下面的 Prim 函数定义节点
struct Node
{
    int u, dis;
    Node() {}
    Node (int _u, int d): u(_u), dis(d) {}
    /// @brief 比较两个Node的大小
    /// @param rhs 右值
    /// @return 如果左值的成员 dis 大于右值,返回 true,否则返回 false
    bool operator<(const Node &rhs) const {
        return dis > rhs.dis;
    }
};

/// @brief Prim算法求最小生成树
/// @return 最小生成树的各边权值之和,如果图不连通,返回 -1
int Prim()
{
    int cnt = 0, ans = 0;
    std::priority_queue<Node> pq;
    pq.push(Node(1, 0));
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    while (!pq.empty())
    {
        if (cnt >= n) {
            break;
        }
        Node tmp = pq.top();
        pq.pop();
        if (vis[tmp.u]) {
            continue;
        }
        vis[tmp.u] = true;
        ++cnt;
        ans += tmp.dis;
        for (int i = head[tmp.u]; i; i = edges[i].next) {
            if (edges[i].weight < dis[edges[i].to]) {
                dis[edges[i].to] = edges[i].weight;
                pq.push(Node(edges[i].to, edges[i].weight));
            }
        }
    }
    return cnt == n ? ans : -1;
}

/// @brief 主函数读入图,调用 Prim 函数求出最小生成树
/// @return 返回 0 表示程序正常结束
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        insert(u, v, w);
        insert(v, u, w);
    }
    int ans = Prim();
    if (ans == -1) {
        printf("orz\n");
    } else {
        printf("%d\n", ans);
    }
    return 0;
}

吸氧结果

不吸氧结果

是不能用 Prim 只能写 Kruskal, 还是我写错了?
不要上来只给个 Kruskal


by szrgjxms @ 2024-08-22 19:07:54

你的边数组开小,要开两倍


by szrgjxms @ 2024-08-22 19:08:52

struct Edge
{
    int from, to, weight, next;
    Edge() {}
    Edge(int f, int t, int w, int n): from(f), to(t), weight(w), next(n) {}
} edges[200010];

这里 200010 改成 400010


by szrgjxms @ 2024-08-22 19:09:53

@Gcc_Gdb_7_8_1


by Gcc_Gdb_7_8_1 @ 2024-08-22 19:29:37

@szrgjxms 谢谢,已关


by Gcc_Gdb_7_8_1 @ 2024-08-22 19:30:24

此贴结


by likunyuan @ 2024-09-07 21:39:05

数据只需开到397043即可


by nineup @ 2024-10-04 16:21:30

@szrgjxms 谢谢orz


|