7-10 公路村村通(并查集kruskal)

7-10 公路村村通(并查集kruskal)最小生成树题目链接现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。输入格式:输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。输出格式:输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出−1,表示需要建设更多公路。输入样例:6 151 2 51 3 3

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

最小生成树

题目链接

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

输入格式:
输入数据包括城镇数目正整数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

C++代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
struct Edge{ 
   
    int u,v,w;
    bool operator<(const Edge &edge)const{ 
   
        return w < edge.w;
    }
}edge[M];
int fa[N],n,m;
void init(){ 
   
    for(int i = 0;i < n;i ++)fa[i] = i;
}
int Find(int x){ 
   
    return fa[x] = (x == fa[x] ? x : Find(fa[x]));	//压缩路径并查集
}
int main(){ 
   
    cin>>n>>m;
    init();
    int x,y,w;
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y>>w;
        edge[i].u = x;
        edge[i].v = y;
        edge[i].w = w;
    }
    sort(edge,edge + m);
    int res = 0,cnt = 0;
    for(int i = 0;i < m;i ++){ 
   
        int X = Find(edge[i].u),Y = Find(edge[i].v);
        if(X != Y){ 
   
            fa[X] = Y;
            res += edge[i].w;
            cnt ++;
        }
    }
    if(cnt != n - 1)cout<< -1;
    else cout<<res;
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168794.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 也谈谈动态绑定dropdownlist(1)

    也谈谈动态绑定dropdownlist(1)说来,很多的dropdownlist选项都不是固定的,是会动态改变的,一种方法是在页面上写死,改变时,直接修改页面就可以了。但是很多人是使用动态绑定的,因此dropdownlist的Text和Valu

  • pycharm创建django项目报错[通俗易懂]

    pycharm创建django项目报错[通俗易懂]ErrorcreatingDjangoapplication:Erroronpythonside.Exitcode如果创建Django项目的时候出现如上截图错误,则是Django下载失败,需要检查本机django是否下载成功,有的时候是因为缺少pytz包而导致django下载失败解决方案:关于pytz包缺失error:CouldnotfindsuitabledistributionforRequirement.parse(‘pytz’)首先去官网下载pytz包:http

    2022年10月31日
  • 导航上显示某个地点已关闭什么意思_大众MIB(275)教程之导航使用「建议收藏」

    导航上显示某个地点已关闭什么意思_大众MIB(275)教程之导航使用「建议收藏」大众可以说近几年的发展非常快,仅车载收音机都更换了好几代了。从最初的单纯收音机到后来的6碟CD机RCD510,最初国内上市的导航RNS510,还有后来自带蓝牙的RNS315,再到PQ平台187A,当初抄的也是火的很几乎每天都能看到187A的帖子,直到出现了升级版的187B,这个自带carplay和百度canlife的PQ平台的机器一下将老款车型导航的改装推上了最巅峰,也把一款拆车机…

  • 手机安装busybox教程(去除busybox的xbin连接)

    Busybox,大家应该有所耳闻,其中集成了众多linux的命令和工具。有时候在手机上想使用find,grep等命令但是手机不支持。这时可以在手机上安装busybox.使用方法:1.确定手机型号cpu的指令集,cat/proc/cpuinfo如armv7,armv4,armv6,去网上下载二进制busybox文件。下载地址:http:

  • 从零开始的 Android 开发[通俗易懂]

    从零开始的 Android 开发[通俗易懂]文章目录0、简介0.1个人情况0.2现状0.3展望0.4一些问题(IDE/编程语言)0.5更新日志0、简介0.1个人情况先说一说自己的情况吧。某985大学的本科学生,因为对Android开发感兴趣,所以先学习了Java(教材是《疯狂Java讲义》,这本书非常好),之后又开始按照郭霖先生的《第一行代码(第二版)》学习Android开发。《疯狂…

  • linux mysql 查看默认端口号和修改端口号

    linux mysql 查看默认端口号和修改端口号

    2021年10月19日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号