请选择 进入手机版 | 继续访问电脑版

洛谷题单——【图论2-3】最小生成树

[复制链接]
盛夏丨光年丶 发表于 2021-1-2 19:44:45 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
P3366 【模板】最小生成树

一道模板题,prim算法就可以过,krustal算法也是可以的嗷
prim算法
[code]#include using namespace std;const int N = 5010;const int INF = 0x3f3f3f3f;int n, m;int g[N][N];int dist[N];bool st[N];int prim(){    memset(dist, 0x3f, sizeof(dist));    int res = 0;    for (int i = 0; i < n; i++)    {        int t = -1;        for (int j = 1; j  dist[j]))                t = j;        }        if (i && dist[t] == INF) return INF;        if(i) res+=dist[t];        for(int j=1;j> n >> m;    memset(g, 0x3f, sizeof(g));    for (int i = 0; i < m; i++)    {        int a, b, w;        cin >> a >> b >> w;        g[a] = g[a] = min(g[a], w);    }    int t = prim();    if (t == INF) cout > a >> b >> w;        edges = {a, b, w};    }    sort(edges, edges + m);    for (int i = 1; i > a >> b >> w;        edges = {a, b, w};    }    sort(edges, edges + m);    for (int i = 1; i  edges.a >> edges.b >> edges.w;    for (int i = 1; i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )