AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 吐槽
  • App
  • 登录/注册

AcWing 试题D. 第十三届蓝桥杯模拟赛(第三期)    原题链接    简单

作者: 作者的头像   HYL_7 ,  2022-11-25 19:43:18 ,  所有人可见 ,  阅读 90


0


问题描述

下面是一个8个结点的无向图的邻接矩阵表示,其中第 i 行第 j 列表示结点 i 到结点 j 的边长度。当长度为 0 时表示不存在边。
请问,这个图的最小生成树大小的多少?

样例

0 9 3 0 0 0 0 9
9 0 8 1 4 0 0 0
3 8 0 9 0 0 0 0
0 1 9 0 3 0 0 5
0 4 0 3 0 7 0 6
0 0 0 0 7 0 5 2
0 0 0 0 0 5 0 4
9 0 0 5 6 2 4 0
/*
  Kruskal算法
   kruscal算法是用于生成最小生成树的常见算法,
   最小生成树也就是在包含图中所有节点的树中,边权和最小的那棵树
        将所有的边长按从小到大排列,每次取最小的边连接两节点,
            若两节点已经处于连通状态,则不连接
                循环上面的步骤,知道所有节点都已经连通,所有边之和就是答案
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int n = 8;
int p[n],ans = 0;

vector<pair<int,int>> a;

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    for(int i = 0;i < n ; i ++) p[i] = i;

    for(int i = 0 ; i < n ; i ++)
        for(int j = 0; j < n ; j ++)
        {
            int len;
            cin >> len;
            if(len) a.push_back({len,i * 100 + j});
        }
        sort(a.begin(),a.end());
        for(int i = 0 ; i < a.size() ; i ++)
        {
            int len = a[i].first;
            int x = a[i].second / 100;
            int y = a[i].second % 100;
            if(find(x) != find(y))
            {
                p[p[x]] = p[y];
                ans += len;
                printf("%d --> %d (%d)\n", x, y, len);
            }
        }

    cout << ans << endl;
    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息