PTA 数据结构与算法题目集(中文) 7-10 公路村村通 (30分) 最小生成树(kruskal算法)
2023-06-13 09:16:58 时间
我的GIS/CS学习笔记:https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes <一个浙江大学本科生的计算机、地理信息科学知识库 > 还有不少数据结构和算法相关的笔记以及pta题解哦x
克鲁斯卡尔算法的基本思想是以边为主导地位,始终选择当前可用的最小边权的边(可以直接快排或者algorithm的sort)。每次选择边权最小的边链接两个端点是kruskal的规则,并实时判断两个点之间有没有间接联通。
PTA题目
现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数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
//Kruskal算法
#include<stdio.h>
#include<stdlib.h>
struct road{
int v1;
int v2;
int cost;
} e[3004];//数组排序并选取最小值;
int v[1001]={0};
int sort(const void *a,const void *b){
return ((struct road*)a)->cost-((struct road*)b)->cost;
}
int root(int x){
if(v[x]==0) return x;
else return v[x]=root(v[x]);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
int i;
for(i=0;i<m;++i)
scanf("%d %d %d",&e[i].v1,&e[i].v2,&e[i].cost);
qsort(e,m,sizeof(struct road),sort);
int sum=0;
//并查集
for(i=0;i<m;i++){
if(root(e[i].v1)!=root(e[i].v2)){
v[root(e[i].v2)]=root(e[i].v1);// 路径压缩
sum+=e[i].cost;
}
}
int flag=1;
for(i=1;i<=n;i++){
if(v[i]==0&&flag) flag=0;
else if(v[i]==0) break;
}
if(i<=n) printf("-1");
else
printf("%d",sum);
}
相关文章
- EasyDSS提示所配置路径不能包含中文的处理方法
- god is a girl 中文意思_π字符
- Theine for mac(防系统休眠工具)v3.5中文激活版
- PTA 数据结构与算法题目集(中文)7-14 电话聊天狂人 (25分) 题解
- Java 随机生成中文姓名,手机号,邮编,住址详解编程语言
- JFreechart在linux下不显示及中文乱码问题详解编程语言
- 使用jfreechart开发的图像,linux系统中文乱码详解编程语言
- Linux系统下实现中文输入的步骤(linux输入中文)
- 25字中文文章标题:深度剖析Linux硬盘文件系统(linux硬盘文件系统)
- 如何解决Redis抖动问题?——25字中文文章标题(redis抖动)
- 嵌入式Linux:让中文应用更便捷(嵌入式linux中文)
- Oracle防火墙端口设置攻略,25字中文文章标题。(oracle防火墙端口)
- 解决Oracle中文显示乱码的方法(oracle中文显示乱码)
- Oracle中文字符串存储的限制分析(oracle中文存储长度)
- Oracle中文字符搜索解决复杂问题的有效方式(oracle中文字符搜索)
- php字符串截取中文截取2,单字节截取模式
- jQueryUIAutocomplete1.8.16中文输入修正代码