AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 858. Prim算法求最小生成树[链式前向星]    原题链接    简单

作者: 作者的头像   Kylin ,  2019-10-02 00:29:25 ,  阅读 547


2



#include<bits/stdc++.h>
using namespace std;
const int maxm = 200005;
const int inf = 0x3f3f3f3f;
struct edge{
    int v, w, next;
}e[maxm << 1];
int cnt, n, m, sum, t, p, now = 1;
int dis[5005], head[maxm], vis[5005];
int a, b, c;

void add(int uu, int vv, int ww)
{
    e[++cnt].v = vv;
    e[cnt].w = ww;
    e[cnt].next = head[uu];
    head[uu] = cnt;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        add(a, b, c); add(b, a, c); // 无向图,所以两个点之间连上 
    }
    for(int i = 1; i <= n; i++)
        dis[i] = inf;
    for(int i = head[1]; i; i = e[i].next) // 判断重边 
        dis[e[i].v] = min(e[i].w, dis[e[i].v]);
    while(++t < n)
    {
        vis[now] = 1;
        int minn = inf;
        now = -1;
        for(int i = 1; i <= n; i++)
        {
            if(!vis[i] && minn > dis[i])
            {
                minn = dis[i];
                now = i;
            }
        }
        if(now == -1) // 若有一个点更新完后dis[]数组仍为 inf,那么不能构成最小生成树 
        {
            cout << "impossible";
            return 0;
        }
        sum += minn;
        for(int i = head[now]; i; i = e[i].next) //更新dis[]数组 
        {
            if(!vis[e[i].v] && e[i].w < dis[e[i].v])
                dis[e[i].v] = e[i].w;
        }
    }
    cout << sum;
    return 0;
}

3 评论


用户头像
yxc   2019-10-01 17:12     回复

这里用的是markdown语法,代码的前面和后面需要加上```才可以正常显示~

用户头像
Kylin   2019-10-02 14:40     回复

ok了,谢谢大佬

用户头像
yxc   2019-10-02 15:18    回复了 Kylin 的评论     回复

很棒!

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息