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

2023-11-24 17:52
文章标签 建设 数据结构 道路 ver

本文主要是介绍【数据结构】F : 道路建设 (Ver. I),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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;
}

这篇关于【数据结构】F : 道路建设 (Ver. I)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/422349

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步

【信创建设】信息系统信创建设整体技方案(word原件完整版)

信创,即“信息技术应用创新”。我国自主信息产业聚焦信息技术应用创新,旨在通过对IT硬件、软件等各个环节的重构,基于我国自有IT底层架构和标准,形成自有开放生态,从根本上解决本质安全问题,实现信息技术可掌控、可研究、可发展、可生产。信创发展是一项国家战略,也是当今形势下国家经济发展的新功能。信创产业发展已经成为各行各业数字化转型、提升产业链发展的关键。 软件全套资料部分文档清单: 工作安排任

模具要不要建设3D打印中心

随着3D打印技术的日益成熟与广泛应用,模具企业迎来了自建3D打印中心的热潮。这一举措不仅为企业带来了前所未有的发展机遇,同时也伴随着一系列需要克服的挑战,如何看待企业引进增材制造,小编为您全面分析。 机遇篇: 加速产品创新:3D打印技术如同一把钥匙,为模具企业解锁了快速迭代产品设计的可能。企业能够迅速将创意转化为实体模型,缩短产品从设计到市场的周期,抢占市场先机。 强化定制化服务:面