7-9 公路村村通

news/2024/11/4 13:35:32/

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

输入格式:
输入数据包括城镇数目正整数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<algorithm>
using namespace std;
typedef struct
{int data;int tou ;int wei ;
} Bian;
bool pai (Bian a,Bian b)
{return a.data<b.data;
}
int main( )
{int n,m;cin>>n>>m;int City[n+1];for(int i=1; i<=n; i++){City[i]=i;}Bian * bian=new Bian [m+1];for(int i=1; i<=m; i++){cin>>bian[i].tou>>bian[i].wei>>bian[i].data;}sort(bian+1,bian+m+1,pai);int sum =0;int cont =0;for(int i=1; i<=m; i++){int tou = bian[i].tou;int wei = bian[i].wei;if(City[tou]!=City[wei]){sum+=bian[i].data;cont ++;for(int j=1; j<=n; j++){if(City[j]==City[wei]&&j!=wei){City[j]=City[tou];}}City[wei]=City[tou];}}if(cont==n-1){cout <<sum;}else{cout <<-1;}return 0;
}

http://www.ppmy.cn/news/857070.html

相关文章

关于卫星互联网的最强入门科普

小枣君&#xff1a;今天这篇文章&#xff0c;是《风雨沧桑50年&#xff1a;中国卫星通信的发展历程》系列文章的最后一篇&#xff08;下篇&#xff09;。 最近十年以来&#xff0c;整个社会对卫星通信的关注度不断提升&#xff0c;各种新闻报道层出不穷。 究其原因&#xff0c;…

09-最小生成树 公路村村通

现有村落间道路的统计数据表中&#xff0c;列出了有可能建设成标准公路的若干条道路的成本&#xff0c;求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数N&#xff08;≤1000&#xff09;和候选道路数目M&#xff08;≤3N&#xff09;&…

DS村村通工程(Kruskal算法)

题目描述 "村村通"是国家一个系统工程&#xff0c;其包涵有&#xff1a;公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。 村村通公路工程&#xff0c;是国家为构建和谐社会&#xff0c;支持新农村建设的一项重大举措&#xff0c;是一项民心工程。又称…

P1536 村村通题解【并查集】

村村通 题目描述 某市调查城镇交通状况,得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 “村村通工程” 的目标是使全市任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要相互之间可达即可)。请你计算出最少还需要建设多少条道路? 输入…

村村通 c语言实现

村村通设计系统 设计目的 在计算机科学中&#xff0c;数据结构是一般程序设计的基础。通过综合设计&#xff0c;使学生学会分析研究数据结构的特征&#xff0c;以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法&#xff0c;掌握算法的时间复杂度分析技术。另一方…

DS村村通工程(Prim算法)

题目描述 "村村通"是国家一个系统工程&#xff0c;其包涵有&#xff1a;公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。 村村通公路工程&#xff0c;是国家为构建和谐社会&#xff0c;支持新农村建设的一项重大举措&#xff0c;是一项民心工程。又称…

公路村村通——求最小生成树

题目描述 现有村落间道路的统计数据表中&#xff0c;列出了有可能建设成标准公路的若干条道路的成本&#xff0c;求使每个村落都有公路连通所需要的最低成本。 输入 输入数据包括城镇数目正整数N&#xff08;≤1000&#xff09;和候选道路数目M&#xff08;≤3N&#xff09;…

P1536 村村通 并查集

题目&#xff1a; 样例&#xff1a; input: 4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0 output: 1 0 2 998 思路&#xff1a; 如果道路数量为0&#xff0c;则直接输出n-1。如果不为0&#xff0c;则在输入后&#xff0c;求出有几个fa,然后-1(把几个fa连起来所需的线条个…