poj2485高速公路

￡神魔★判官ぃ 2022-06-18 08:39 152阅读 0赞

#include <iostream>
    #define MAX 502
    using namespace std;
    int str[MAX][MAX];
    bool visit[MAX];//标记数组，没有加入到树中时为false,加入了为true
    int distan[MAX];//用以记录当前树到各个顶点的最小距离（它会被不断的更新，加入一个顶点更新一次）
    int n;
    int prim()//prim算法
    {
        
        int v,i,j,maxi=0;
        visit[0]=true;//将第一个顶点加入树中
        for(i=0;i<n;i++)//计算只有一个顶点时的distan[i]
            distan[i]=str[0][i];
        
        for(j=1;j<n;j++)
        {
        
            int mini=65550;
            for (i=0;i<n;i++)//找最小的边
            {
        
                if(visit[i]==false&&distan[i]<mini)//找出没有在当前树中且权值最小的点
                {
        
                    mini=distan[i];
                    v=i;
                }
            }
            //cout<<mini<<' ';
            visit[v]=true;//标记顶点v,加入生成树中
            if(maxi<mini)
                maxi=mini;
            for (i=0;i<n;i++)//将生成树的权值更新
            {
        
                if(visit[i]==false&&distan[i]>str[v][i])//distan[i]中始终放生成树到顶点i的最小权值
                {
        
                    distan[i]=str[v][i];
                }
            }
        }
        return maxi;
    }
    
    int main()
    {
        
        int i,j,t;
        cin>>t;
        while(t--)
        {
        
            cin>>n;
            for(i=0;i<n;i++)
                visit[i]=false;
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                    scanf("%d",&str[i][j]);
                cout<<prim()<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关区间贪心：最小区间覆盖问题、PIPI的高速公路

区间贪心：最小区间覆盖问题、PIPI的高速公路文章目录区间贪心：最小区间覆盖问题、PIPI的高速公路问题1：思

刺骨的言语ヽ痛彻心扉/ 2023年10月06日 20:19/ 0 赞/ 30 阅读

相关中国公路经营模式

author:skate time:2011-02-25 -------------------- csdn怎么搞的，还丢数据啊，昨天发的文章，今天看就没了。太没保障了！

深碍√TFBOYSˉ_/ 2022年09月29日 05:26/ 0 赞/ 157 阅读

相关 POJ 2485-Highways(最小生成树裸题-prim/kruskal)

Highways <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

向右看齐/ 2022年08月22日 15:27/ 0 赞/ 79 阅读

相关 Maven高速镜像

家都知道国外Maven中央仓库下载东西龟速；这里提供下国内牛逼的Maven镜像阿里云Maven镜像；配置下setting.xml即可；

深碍√TFBOYSˉ_/ 2022年07月12日 05:19/ 0 赞/ 119 阅读

相关 poj2485高速公路

include <iostream> define MAX 502 using namespace std; int str[MAX][MAX]

￡神魔★判官ぃ/ 2022年06月18日 08:39/ 0 赞/ 153 阅读

相关村村通公路（Prim）

数据结构实验之图论六：村村通公路 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem

以你之姓@/ 2022年06月05日 08:27/ 0 赞/ 190 阅读

相关 poj--2485--Highways

Highways <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td

爱被打了一巴掌/ 2022年06月03日 01:17/ 0 赞/ 119 阅读

相关 POJ2485 Highways——————最小生成树

Highways <table> <tbody> <tr> <td> <div> Language:Default </di

淡淡的烟草味﹌/ 2022年05月16日 06:27/ 0 赞/ 173 阅读

相关高速CDN

[admin-lte | BootCDN – Bootstrap 中文网开源项目免费 CDN 加速服务][admin-lte _ BootCDN _ Bootstrap _ C

￡神魔★判官ぃ/ 2022年03月20日 13:42/ 0 赞/ 250 阅读

相关 CCF 高速公路

一、试题问题描述　　某国有n个城市，为了使得城市间的交通更便利，该国国王打算在城市之间修一些高速公路，由于经费限制，国王打算第一阶段先在部分城市之间修一些单向的高

红太狼/ 2021年09月14日 03:12/ 0 赞/ 291 阅读