NOI大纲——提高组——最小生成树

2024-08-21 04:12
文章标签 大纲 最小 生成 提高 noi

本文主要是介绍NOI大纲——提高组——最小生成树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最小生成树

简介

一个图中可能存在多条相连的边,我们**一定可以从一个图中挑出一些边生成一棵树。**这仅仅是生成一棵树,还未满足最小,当图中每条边都存在权重时,这时候我们从图中生成一棵树(n - 1 条边)时,生成这棵树的总代价就是每条边的权重相加之和。

一个有N个点的图,边一定是大于等于N-1条的。图的最小生成树,就是在这些边中选择N-1条出来,连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

应用

1.城市规划

要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树

2.游戏开发

游戏的本质其实都是迷宫,比如王者荣耀的地图,以俯视的角度来看,他就是一个迷宫,只不过进行了建模,而对于每一个迷宫,必须要联通,也就是要走的通,那么我们就可以使用最小生成树的算法了。

Prim 普里姆算法

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 505;int a[maxn][maxn];//临界矩阵存储
int vis[maxn],dist[maxn];//vis为标记数组,dist为距离数组
int n,m;
int u,v,w;
long long sum = 0;//存储答案// 使用 Prim 算法计算最小生成树的权值和
int prim(int pos) {dist[pos] = 0;  // 初始化,将起始点到自身的距离设为 0// 一共有 n 个点,需要遍历 n 次,每次寻找一个权值最小的点,记录其下标for(int i = 1; i <= n; i++) {int cur = -1;  // 用于记录当前找到的最小距离的点的下标// 寻找未访问过的点中距离最小的点for(int j = 1; j <= n; j++) {if(!vis[j] && (cur == -1 || dist[j] < dist[cur])) {cur = j;  // 更新当前最小距离的点的下标}}// 如果最小的距离都为极大值则不可能形成最小生成树,提前终止if(dist[cur] >= INF) return INF;sum += dist[cur];  // 记录答案,将当前找到的最小距离加入到最小生成树的权值和中vis[cur] = 1;  // 标记当前找到的最小距离的点为已访问// 更新与当前找到的最小距离的点相连的其他点的距离for(int k = 1; k <= n; k++) {// 只更新还没有找到的最小权值if(!vis[k]) dist[k] = min(dist[k], a[cur][k]);}}return sum;  // 返回最小生成树的权值和
}int main() {cin>>n>>m;memset(a,0x3f,sizeof(a));memset(dist,0x3f,sizeof(dist));//附上极大值for(int i = 1; i <= m; i ++) {cin>>u>>v>>w;a[u][v] = min(a[u][v],w);a[v][u] = min(a[v][u],w);//去除重边}int value = prim(1);if(value >= INF) cout<<"impossible";else cout<<sum;return 0;
} 

Kruskal 克鲁斯卡尔算法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10; 
struct node {int x,y,z;
}edge[maxn];
bool cmp(node a,node b) {return a.z < b.z;//以长度为基准
}
int fa[maxn];
int n,m;
int u,v,w; 
long long sum;int get(int x) {//并查集找祖宗return x == fa[x] ? x : fa[x] = get(fa[x]);
}int main() {cin>>n>>m;for(int i = 1; i <= m; i ++) {cin>>edge[i].x>>edge[i].y>>edge[i].z;}for(int i = 0; i <= n; i ++) {//并查集初始化fa[i] = i;}sort(edge + 1,edge + 1 + m,cmp);//排序// 每次加入一条最短的边for(int i = 1; i <= m; i ++) {int x = get(edge[i].x);int y = get(edge[i].y);//找祖宗if(x == y) continue;//如果祖宗一样则为环,所以跳过fa[y] = x;//合并sum += edge[i].z;//存储答案}int ans = 0;for(int i = 1; i <= n; i ++) {if(i == fa[i]) ans ++;//如果有点没有被最小生成树所包含,则增加}if(ans > 1) cout<<"impossible";//按理来说应该只有一个,也就是所有人的祖先else cout<<sum;return 0;
} 

这篇关于NOI大纲——提高组——最小生成树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python如何生成指定文件大小

《python如何生成指定文件大小》:本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin(推荐)的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事

Java使用MethodHandle来替代反射,提高性能问题

《Java使用MethodHandle来替代反射,提高性能问题》:本文主要介绍Java使用MethodHandle来替代反射,提高性能问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录一、认识MethodHandle1、简介2、使用方式3、与反射的区别二、示例1、基本使用2、(重要)

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤:代码片段:2. 应用 JSON 样式到

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC(MediaAccessControl)地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I

PyQt5+Python-docx实现一键生成测试报告

《PyQt5+Python-docx实现一键生成测试报告》作为一名测试工程师,你是否经历过手动填写测试报告的痛苦,本文将用Python的PyQt5和python-docx库,打造一款测试报告一键生成工... 目录引言工具功能亮点工具设计思路1. 界面设计:PyQt5实现数据输入2. 文档生成:python-

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注