数字4挺好(dzf) 2022-01-12 18:36 采纳率: 0%
浏览 8
已结题

洛谷P3366 【模板】最小生成树 RE三个点为什么

    // prim 算法求最小生成树 
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define INF 0x3f3f3f3f
    using namespace std;
    const int maxn = 505;
    int a[maxn][maxn];
    int vis[maxn],dist[maxn];
    int n,m,u,v,w;
    long long sum = 0;
    int prim(int pos) {
        dist[pos] = 0;
        for(int i = 1; i <= n; i ++) {
            int cur = -1;
            for(int j = 1; j <= n; j ++)
                if(!vis[j] && (cur == -1 || dist[j] < dist[cur])) cur = j;
            if(dist[cur] >= INF) return INF;
            sum += dist[cur];
            vis[cur] = 1;
            for(int k = 1; k <= n; k ++) 
                if(!vis[k]) dist[k] = min(dist[k],a[cur][k]);
        }
        return sum;
    }
    int main(void) {
        scanf("%d%d",&n,&m);
        memset(a,0x3f,sizeof(a));                                                                 
        memset(dist,0x3f,sizeof(dist));
        for(int i = 1; i <= m; i ++) {
            scanf("%d%d%d",&u,&v,&w);
            a[u][v] = min(a[u][v],w);
            a[v][u] = min(a[v][u],w);
        }
        int value = prim(1);
        if(value >= INF) puts("orz");
        else printf("%lld\n",sum);
        return 0;
    }

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 1月20日
    • 创建了问题 1月12日

    悬赏问题

    • ¥15 有两个非常“自以为是”烦人的问题急期待大家解决!
    • ¥30 STM32 INMP441无法读取数据
    • ¥100 求汇川机器人IRCB300控制器和示教器同版本升级固件文件升级包
    • ¥15 用visualstudio2022创建vue项目后无法启动
    • ¥15 x趋于0时tanx-sinx极限可以拆开算吗
    • ¥15 pyqt信号槽连接写法
    • ¥500 把面具戴到人脸上,请大家贡献智慧,别用大模型回答,大模型的答案没啥用
    • ¥15 任意一个散点图自己下载其js脚本文件并做成独立的案例页面,不要作在线的,要离线状态。
    • ¥15 各位 帮我看看如何写代码,打出来的图形要和如下图呈现的一样,急
    • ¥30 c#打开word开启修订并实时显示批注