PTA 数据结构与算法题目集(中文) 7-10 公路村村通 (30分) 最小生成树(kruskal算法)
2023-03-07 09:08:28 时间
我的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);
}
相关文章
- 建立 VPC 并基于参数动态创建子网的 CloudFormation 模板
- 物联网设备全球部署架构方案
- AWS IoT 物联网系列 | 第七篇:AWS IoT Core服务成本优化
- AWS IoT 物联网系列 | 第八篇:Alexa 入门实验
- AWS IoT 物联网系列 | 第二篇:使用模版自动化 IoT 设备创建及证书注册过程 (Just-In-Time Provisioning)
- AWS IoT 物联网系列 | 第一篇:利用 Lambda 实现 IoT 设备证书的即时注册 (Just-In-Time Registration)
- 如何将亚马逊 AWS S3 存储桶的访问权限到一个特定 IAM 角色
- 怎样利用 AWS Config 监控和响应 Amazon Simple Storage Service (S3) 允许公开读写访问权限
- AWS CodeBuild 将提供本地构建支持
- 如何实现对集群任务最小影响的 ECS 容器实例自动化终止方案
- 针对 Amazon CloudFront 请求的增强域保护
- 使用 Amazon Comprehend 和 Amazon Relational Database Service 构建文本分析解决方案
- 使用 AWS SMS 将 SAP 迁移到 AWS
- EC2 实例更新 – 配备本地 NVMe 存储的 C5 实例 (C5d)
- AWS IoT 1-Click – 使用简单设备触发 Lambda 函数
- OpenSource | 使用 AWS Service Broker 通过 Kubernetes 配置 AWS 服务
- OpenSource | 将 Heptio Authenticator 部署到 kops
- Amazon Sumerian – 现已全面开放
- 利用 AWS Comprehend 打造近实时文本情感分析
- OpenSource | 使用 virtual-kubelet 运行 AWS Fargate