【数据结构】F : 道路建设 (Ver. I)

news/2025/3/31 5:58:24/

F : 道路建设 (Ver. I)

Description

有N个村庄,编号从1到N,你应该建造一些道路,使每个村庄都可以相互连接。
两个村A和B是相连的,当且仅当A和B之间有一条道路,或者存在一个村C使得在A和C之间有一条道路,并且C和B相连。
现在一些村庄之间已经有一些道路,你的任务就是修建一些道路,使所有村庄都连通起来,并且所有道路的长度总和是最小的。

Input

测试数据有多组
第一行是整数N(3 <= N <= 100),代表村庄的数量。 然后是N行,其中第i行包含N个整数,这些N个整数中的第j个是村庄i和村庄j之间的距离(距离是[1,1000]内的整数)。
然后是整数Q(0 <= Q <= N *(N + 1)/ 2),接下来是Q行,每行包含两个整数a和b(1 <= a <b <= N),代表着村庄a和村庄b之间的道路已经建成。

Output

对于每组测试数据
输出一个整数,表示要构建的道路的长度总和最小值

Sample

Input
3
0 990 692
990 0 179
692 179 0
1
1 2
Output
179

解题思路

最小生成树啊,连接所有点并且让他们的权值之和最小,这里面需要注意的就是已经修好路的两村庄的处理,而且这还是无向图,也就是要处理两次,并且距离设为很小的数比较好。思路就是这些了,剩下的就找个prim算法或者kruscal操一下,输出最小值。

AC代码

#include <iostream>
#include <vector>
#include <limits>
using namespace std;const double MAX_WEIGHT = numeric_limits<double>::max();
const double ALREADY_CONNECTED = 1e-7;int PrimMinimumSpanningTree(const vector<vector<double>>& graph) {int n = graph.size();vector<double> key(n, MAX_WEIGHT);vector<bool> includedInMST(n, false);key[0] = 0;int totalWeight = 0;for (int count = 0; count < n; count++) {double minKey = MAX_WEIGHT;int minKeyNode = -1;for (int v = 0; v < n; v++) {if (!includedInMST[v] && key[v] < minKey) {minKey = key[v];minKeyNode = v;}}includedInMST[minKeyNode] = true;totalWeight += key[minKeyNode];for (int v = 0; v < n; v++) {if (graph[minKeyNode][v] && !includedInMST[v] && graph[minKeyNode][v] < key[v]) {key[v] = graph[minKeyNode][v];}}}return totalWeight;
}int main() {int n;while (cin >> n) {vector<vector<double>> graph(n, vector<double>(n));for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> graph[i][j];int m;cin >> m;for (int i = 0; i < m; i++) {int a, b;cin >> a >> b;graph[a - 1][b - 1] = graph[b - 1][a - 1] = ALREADY_CONNECTED;}cout << PrimMinimumSpanningTree(graph) << endl;}return 0;
}

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

相关文章

ElasticSearch的日志配置

ElasticSearch默认情况下使用Log4j2来记录日志&#xff0c;日志配置文件的路径为$ES_HOME/config/log4j2.properties&#xff0c;配置方法见Log4j2的官方文档。 参考path-settings&#xff0c;通过指定path.logs&#xff0c;可以指定日志文件的保存路径。 在日志配置文件$ES_…

Design Guidelines for 100 Gbps

文章目录 Stratix V GT Transceiver ChannelsCFP2 Host Connector Assembly and PinoutStratix V GT to CFP2 Interface Layout DesignBoard Stack Up DimensionsExample Design Channel PerformanceSimulation Results for Stratix V GT to CFP2 Connector Layout Design Desi…

⑩⑧【MySQL】InnoDB架构、事务原理、MVCC多版本并发控制

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ InnoDB存储引擎 ⑩⑧【MySQL】详解InnoDB存储引…

Vue批量全局处理undefined和null转为““ 空字符串

我们在处理后台返回的信息&#xff0c;有的时候返回的是undefined或者null&#xff0c;这种字符串容易引起用户的误解&#xff0c;所以需要我们把这些字符串处理一下。 如果每个页面都单独处理&#xff0c;那么页面会很冗余&#xff0c;并且后期如果有修改容易遗漏&#xff0c…

Java中基于SSM框架的数据保存方法与日期处理

​ 一、详解 在SSM框架中&#xff0c;保存数据通常涉及到服务层和数据访问层。服务层处理业务逻辑&#xff0c;而数据访问层负责与数据库进行交互。 二、代码 Override public void save(Student student) { Date date new Date(); SimpleDateFormat format new Sim…

linux(nginx安装配置,tomcat服务命令操作)

首先进系统文件夹 /usr/lib/systemd/systemLs | grep mysql 查看带有命名有MySQL的文件夹修改tomcat.service文件复制jdk目录替换成我们的路径替换成我们的路径进入这个目录&#xff0c;把修改好的文件拖到我们的工具里面重新刷新系统 systemctl daemon-reload查看tomcat状态…

redis的集群,主从复制,哨兵

redis的高可用 在Redis中&#xff0c;实现高可用的技术主要包括持久化、主从复制、哨兵和集群&#xff0c;下面分别说明它们的作用&#xff0c;以及解决了什么样的问题。 持久化&#xff1a; 持久化是最简单的高可用方法&#xff08;有时甚至不被归为高可用的手段&#xff09;…

快速学会使用Python3.12的新特性

一、 PEP 695: 类型形参语法的革新 PEP 695 在 Python 3.12 中引入了一种新颖且更为清晰的方式来定义泛型类和函数&#xff0c;旨在提升类型参数的明确性和简洁性。这个提案不仅改善了类型系统的可读性&#xff0c;还增强了其功能性。以下是这些变化的详细概述&#xff1a; 1…