首页 > 编程语言 >7-10 公路村村通 Prim算法

7-10 公路村村通 Prim算法

时间:2024-03-22 23:32:51浏览次数:30  
标签:10 Prim 输出 int 公路 道路 dist 输入 村村通

现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出−1,表示需要建设更多公路。

输入样例:

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

输出样例:

12
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1100;
#define INF 0x3f3f3f3f
int g[N][N];
int n,m;
int res;
int dist[N];
bool st[N];
void prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    for(int i=0;i<n;i++)
    {
        int t = -1;
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1||dist[j]<dist[t])) t = j;

        st[t] = true;
        res += dist[t];
        for(int j=1;j<=n;j++)
            dist[j] = min(dist[j],g[t][j]);

    }
}
int main()
{
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    while(m--)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u][v] = g[v][u] = min(g[u][v],w);
    }
    prim();
    
    res >=INF ? cout<<"-1"<<endl : cout<<res<<endl;
    return 0;
}

 

标签:10,Prim,输出,int,公路,道路,dist,输入,村村通
From: https://blog.csdn.net/qq_62145422/article/details/136880171

相关文章

  • 洛谷题单指南-集合-P1525 [NOIP2010 提高组] 关押罪犯
    原题链接:https://www.luogu.com.cn/problem/P1525题意解读:有很多罪犯,要关到两座监狱,有一些罪犯之间有仇,并且可以量化出仇恨值,如果关在一起就会冲突,造成的影响就是仇恨值,要使得造成的影响最小,如果可以完全不起冲突,输出0。解题思路:首先,要让冲突影响最小化,显然应该把仇恨大的罪犯......
  • P1075 [NOIP2012 普及组] 质因数分解
    P1075[NOIP2012普及组]质因数分解[NOIP2012普及组]质因数分解题目描述已知正整数\(n\)是两个不同的质数的乘积,试求出两者中较大的那个质数。输入格式输入一个正整数\(n\)。输出格式输出一个正整数\(p\),即较大的那个质数。样例#1样例输入#121样例输出#1......
  • P1055 [NOIP2008 普及组] ISBN 号码
    P1055[NOIP2008普及组]ISBN号码[NOIP2008普及组]ISBN号码题目描述每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括\(9\)位数字、\(1\)位识别码和\(3\)位分隔符,其规定格式如x-xxx-xxxxx-x,其中符号-就是分隔符(键盘上的减号),最后一位是识别码,例如0-6......
  • Github最受欢迎的TOP 10开源RTSP流媒体项目
    Github最受欢迎的TOP10开源RTSP流媒体项目一块程序圆关注IP属地:河南0.1812020.09.2209:45:20字数457阅读6,684Github选出 TOP10开源免费的RTSP流媒体项目,以下是具体排名及星星数。 1、Easydarwin星星数:4,307Easydarwin是国内团队开发的开源流媒体框架......
  • P5741 【深基7.例10】旗鼓相当的对手 - 加强版
    P5741【深基7.例10】旗鼓相当的对手-加强版【深基7.例10】旗鼓相当的对手-加强版题目描述现有\(N(N\le1000)\)名同学参加了期末考试,并且获得了每名同学的信息:姓名(不超过\(8\)个字符的字符串,没有空格)、语文、数学、英语成绩(均为不超过\(150\)的自然数)。如果某对学......
  • B2102 计算鞍点
    B2102计算鞍点计算鞍点题目描述给定一个\(5\times5\)的矩阵,每行只有一个最大值,每列只有一个最小值,寻找这个矩阵的鞍点。鞍点指的是矩阵中的一个元素,它是所在行的最大值,并且是所在列的最小值。例如:在下面的例子中,第\(4\)行第\(1\)列的元素就是鞍点,值为\(8\)。113......
  • 2023-8-10-canal使用
    工作原理、mysql开启二进制日志、启动服务端、启动客户端工作原理canal模拟MySQLslave的交互协议,伪装自己为MySQLslave,向MySQLmaster发送dump协议MySQLmaster收到dump请求,开始推送binarylog给slave(即canal)canal解析binarylog对象(原始为byte流......
  • 2021-4-10-达梦数据库
    模式、状态、状态切换、表空间、GROUPBY、JOIN语句报错、事务模式达梦数据库支持3中模式:Normal模式、Primary模式和Standby模式。1)Normal模式用户可以正常访问数据库,操作没有限制。正常生成本地归档,但不发送实时归档(Realtime)、即时归档(Timely)和异步归档(Async)。将数据......
  • 2021-10-22-go语言基础
    概述、变量、常量、运算符和函数、导包、指针、defer、数组、切片、map、type使用、面向对象、反射、chanel、协程、json操作、随机数、网络编程、读取文件、beego概述1特性:自动垃圾回收更丰富的内置类型函数多返回值错误处理匿名函数和闭包类型和接口并发......
  • 海思 SS927V100 HI3519AV200 简介
    海思SS927V100HI3519AV200简介HI3519AV200是一颗专业ultra-HDSmartIPCameraSOC。SS927V100(另称:22AP70、SD3402)功能以及封装与HI3519AV200完全一致,可以平替HI3519AV200。最高支持四路sensor输入,支持最高4K60的ISP图像处理能力,支持3FWDR、多级降噪、六轴......