简单的稠密图求最小生成树

怼烎@ 2022-12-01 15:38 112阅读 0赞

啊哈算法学习笔记，简单的稠密图求最小生成树问题

#include <cstdio>
    
    using namespace std;
    
    const int inf = 0x7fffffff;
    
    int n;
    int a[500][500];
    int dis[500];
    
    int prim()
    {
        
        int ans=0,cnt=0;
        int k,min_road;
    
        ++cnt;
        for(int i=0;i<n;++i)
        {
        
            dis[i]=a[0][i];
        }
        while(cnt<n)
        {
        
            min_road=inf;
            for(int i=0;i<n;++i)
            {
        
                // 选出最小的一条边
                if(dis[i]!=0 && dis[i]<min_road)
                {
        
                    min_road=dis[i];
                    k=i;
                }
            }
        }
    }
    
    int main()
    {
        
        int T;
        scanf("%d",&T);
        while(T--)
        {
        
            scanf("%d",&n);
            for(int i=0;i<n;++i)
            {
        
                for(int j=0;j<n;++j)
                {
        
                    scanf("%d",&a[i][j]);
                }
            }
            printf("%d",prim());
        }
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关最小生成树的简单题

古老的最小生成树代码，可以当板子用（针对问题修改一下，不通用，原理一样）。 include <iostream> include <cstdio> i

妖狐艹你老母/ 2022年12月01日 15:39/ 0 赞/ 162 阅读

相关简单的稠密图求最小生成树

啊哈算法学习笔记，简单的稠密图求最小生成树问题 include <cstdio> using namespace std; con

怼烎@/ 2022年12月01日 15:38/ 0 赞/ 113 阅读

相关图的最小生成树算法

在上一篇文章中，我们看了一下图的遍历算法，主要是对图的深度优先遍历和图的广度优先遍历算法思想的介绍。接下来让我们来看一下图的最小声成树算法。首先，我们要知道，图的最小生成树

清疚/ 2022年09月28日 13:03/ 0 赞/ 182 阅读

相关求最小生成树Kruskal算法

求最小生成树Kruskal算法本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。本博文作为学习资料整理。源代码是VC++ 6.0上可执行程

古城微笑少年丶/ 2022年08月21日 04:19/ 0 赞/ 173 阅读

相关 prim求最小生成树——Highways

Highways Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 27038 Accepted:

电玩女神/ 2022年08月21日 03:22/ 0 赞/ 172 阅读

相关图结构练习——最小生成树

图结构练习——最小生成树 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述有n个城市，其中有

刺骨的言语ヽ痛彻心扉/ 2022年08月10日 06:11/ 0 赞/ 156 阅读

相关图的最小生成树

import java.util.Stack; / 图的最小生成树 / public class MSTDemo {

川长思鸟来/ 2022年08月06日 11:11/ 0 赞/ 146 阅读

相关图结构练习——最小生成树

Problem Description 有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，

末蓝、/ 2022年07月12日 09:51/ 0 赞/ 162 阅读

相关图论-最小生成树

给定一个无向图，如果它的某一个子图中任意俩个顶点都互相联通并且是一棵树，那么这棵树就是生成树。如果边上还有权值，边权和最小的称为最小生成树。算法1：Prim算法

深碍√TFBOYSˉ_/ 2022年05月28日 04:51/ 0 赞/ 166 阅读

相关图的应用——最小生成树

最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构。最小生成树可以用Prim（普里姆）算法或kru

野性酷女/ 2021年11月16日 15:10/ 0 赞/ 279 阅读