首页 > 其他分享 >5790: 繁忙的都市 prim最小生成树

5790: 繁忙的都市 prim最小生成树

时间:2023-05-10 21:12:05浏览次数:35  
标签:prim 交叉路口 int 5790 分值 道路 都市 dis

描述

 

城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2.在满足要求1的情况下,改造的道路尽量少。

3.在满足要求1、2的情况下,改造的那些道路中分值最大值尽量小。

作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

 

 

输入

 

第一行有两个整数n,m表示城市有n个交叉路口,m条道路。接下来m行是对每条道路的描述,u, v, c表示交叉路口u和v之间有道路相连,分值为c。(1≤n≤300,1≤c≤10000)。

 

输出

 

两个整数s, max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

 

样例输入

 

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

样例输出

 3 6   思路: 忽视题目的问题,想连通n个点当然要n-1条边,同时要求连接的边权值越短,那就是最小生成树,所以不管是kruskal还是prim算法,都可以每获取一条边就比较较大值maxx即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10,inf = 0x3f3f3f3f;
int dis[N],vis[N],g[N][N],f[N];
int n,m,maxx = -inf;
void prim()
{
    memset(dis,inf,sizeof dis);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)dis[i] = g[1][i],f[i] = 1;
    dis[1] = 0;
    vis[1] = 1;
    int minn,pos;
    for(int i=1;i<=n;i++)
    {
        minn = inf;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0 && minn>dis[j])
            {
                minn = dis[j];pos = j;
            }
        }
        if(minn==inf)break;
        vis[pos] = 1;
        maxx = max(maxx,dis[pos]);
        for(int j=1;j<=n;j++)
            if(vis[j]==0 && dis[j]>g[pos][j])
                dis[j] = g[pos][j];
    }
}
int main()
{
    cin>>n>>m;
    memset(g,inf,sizeof(g));
    for(int i=1;i<=n;i++)g[i][i] = 0;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;cin>>x>>y>>z;
        g[x][y] = g[y][x] = z;
    }
    prim();
    cout<<n-1<<" "<<maxx;
     return 0;
}

 

标签:prim,交叉路口,int,5790,分值,道路,都市,dis
From: https://www.cnblogs.com/jyssh/p/17389349.html

相关文章

  • C++ Primer学习笔记——第二章
    第二章变量和基本类型前言数据类型是程序的基础:它告诉我们数据的意义以及我们能在数据上执行的操作。2.1基本内置类型C++定义了包括算术类型(arithmetictype)和空类型(void)在内的基本数据类型。2.1.1算术类型算术类型分为两类:整型和浮点型。具体分类:类型含义最小容......
  • POJ2739 Sum of Consecutive Prime Numbers&&Acwing4938 连续质数之和
    方法:单调队列为什么是单调队列?因为这里让我们求连续的质数和,我们可以利用欧拉筛来维护质数,再利用单调队列来维护连续的质数。代码(POJ不支持C++11差评):#include<cstdlib>#include<cstring>#include<cstdio>#include<cctype>namespaceFastIo{ #definegcgetchar() #d......
  • 璞华助力“数字人社”,为成都市人社数字化建设提供多方位的产品与技术支持!
    新的时期,人力资源和社会保障事业进入新一轮的制度创新和加快发展阶段。把对各项人力资源和社会保障业务的支持和服务纳入信息化建设,通过“数字人社”信息化建设项目,是充分利用新一代信息技术,有效整合各类信息资源,持续推动市人社信息化建设、支撑人社事业发展的有效途径;有利于促......
  • C Primer Plus 第六版
      取指执行,1秒钟执行10个小目标!!寄存器:存储指令、存储指令地址等指令一般做什么用?移动数据,如从内存移动到寄存器......
  • C++ Primer 5th Edition, Chapter 2, Solutions
    Exercise2.1QuestionsWhatarethedifferencesbetweenint,long,longlong,andshort?Betweenanunsignedandasignedtype?Betweenafloatandadouble?SolutionsThosetypeshavedifferentminimumsizesaslistedinTable2.1.Andadditionalru......
  • C++ Primer 5th 阅读笔记:变量和基本类型
    一些语言的公共特性内建类型,如整型,字符型等;变量,为值绑定的一个名字;表达式和语句,操作值。分支和循环,允许我们条件执行和重复执行;函数,定义抽象计算单元。扩展语言的方式自定义类型;标准库。本章重点学习语言的基本知识和标准库。内建类型;简要介绍自定义类。类型......
  • 都市潜龙(持续更新,由彩云小梦出品)
    "你是什么人?!"邹家的大门被推开,两名壮汉走了进来。"你们找谁?"看到两个穿黑西装的壮汉走进来,管家连忙问道。"邹广琛呢?!"其中一名壮汉冷声道。听到这里,邹管家脸上露出一丝惊讶之色:"先生在书房,请问两位有什么事吗?""没事,我们只是过来通知他一声。"为首那个壮汉说着,就朝楼梯口走去。邹管......
  • 5471: 数据结构实验--图的最小代价生成树 prim
    描述  求带权无向图的最小代价生成树。    输入  输入数据为多组,每组数据包含多行,第一行为2个整数n,e,n为图的顶点数,e为边数,接下来是e行,每行3个整数,前两个整数是一个顶点对,代表一条边所依附的两个顶点,第3个整数是边的权值。所有值不超过20。  输出......
  • 次小生成树(Prim + Kruaskal)
    问题引入:我们先来回想一下生成树是如何定义的,生成树就是用n-1条边将图中的所有n个顶点都连通为一个连通分量,这样的边连成子树称为生成树。最小生成树很明显就是生成树中权值最小的生成树,那么我们即将要学的次小生成树或者K小生成树是怎么定义的呢,很明显就是生成树中权......
  • Quartus Prime-can't launch the ModelSim software 的解决办法
     19.1版本的QuartusPrime Lite版本,安装了免费版的modelsim,已经设置了modelsim的路径: 但是还是提示: 打开Setting这里设置选中Modelsim-Altera 就可以了: ......