2.13学习总结

1.出差（Bleeman—ford）（spfa）
（dijkstra）
2.最小生成树（prim）（Kruskal）

最短路问题：

出差https://www.luogu.com.cn/problem/P8802

题目描述

AA 国有 �N 个城市，编号为 1…�1…N 小明是编号为 11 的城市中一家公司的员工，今天突然接到了上级通知需要去编号为 �N 的城市出差。

由于疫情原因，很多直达的交通方式暂时关闭，小明无法乘坐飞机直接从城市 11 到达城市 �N，需要通过其他城市进行陆路交通中转。小明通过交通信息网，查询到了 �M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。

同样由于疫情原因，小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络，小明也查询到了各个城市的隔离信息。（由于小明之前在城市 11，因此可以直接离开城市 11，不需要隔离）

由于上级要求，小明希望能够尽快赶到城市 NN, 因此他求助于你，希望你能帮他规划一条路线，能够在最短时间内到达城市 �N 。

输入格式

第 11 行：两个正整数 �,�N,M 表示 A 国的城市数量, �M 表示末关闭的路线数量。

第 22 行: �N 个正整数，第 �i 个整数 ��Ci​ 表示到达编号为 ii 的城市后需要隔离的时间。

第 3…�+23…M+2 行: 每行 33 个正整数, �,�,�u,v,c, 表示有一条城市 �u 到城市 �v 的双向路线仍然开通着，通过该路线的时间为 �c。

输出格式

第 11 行：11 个正整数，表示小明从城市 11 出发到达城市 �N 的最短时间。（到达城市 �N，不需要计算城市 �N 的隔离时间）

输入输出样例

输入 #1复制

4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5

输出 #1复制

13

说明/提示

【样例说明】

【评测用例规模与约定】

对于 100%100% 的数据, 1≤�≤1000,1≤�≤10000,1≤��≤200,1≤�,�≤1≤N≤1000,1≤M≤10000,1≤Ci​≤200,1≤u,v≤ �,1≤�≤1000N,1≤c≤1000

Dijkstra算法：

主要是利用邻接表和优先队列实现，总复杂度是O（nlongn）

实现：起点先入队，然后找到所有的邻居入队（除了已经标记了找到最短路的），找后序点的时候，优先选择路径短的点（用优先队列实现）

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f
const int N=20010;
int n,m;
int t[N],dist[N];
struct edge{
	int to;
	int w;
	edge(int a,int b) {
		to=a;
		w=b;
	}	
};
vector<edge>e[N];
struct node{
	int id;
	int n_dis;
	node(int aa,int bb){
		id=aa;
		n_dis=bb;
	}
	bool operator < (const node& a)const{
		return n_dis > a.n_dis;
	}
};
void dijkstra(){
	bool done[N];	//标记数组，用于确定是否该节点找到最短路径 
	for (int i=1;i<=n;++i){
		done[i]=false;
		dist[i]=INF;
	}
	dist[1]=0;	//初始化，起点到起点的距离为0 
	priority_queue<node>q;
	q.push(node(1,dist[1]));
	while (!q.empty()){
		node p=q.top(); q.pop();
		if (done[p.id]) continue;
		done[p.id]=true;
		for (int i=0;i<e[p.id].size();++i){
			int y=e[p.id][i].to;
			int w=e[p.id][i].w;
			if (done[y]) continue;
			int res=t[y];
			if (y==n) res=0;
			if (dist[y]> p.n_dis+w+res){	//当前节点y到起点的最短路径大于路过p点到y点的路径 
				dist[y]=p.n_dis+w+res;
				q.push(node(y,dist[y]));
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for (int i=1;i<=n;++i) cin>>t[i];
	for (int i=0;i<m;++i){	//建立邻接表 
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back(edge(b,c));
		e[b].push_back(edge(a,c));
	}
	dijkstra();
	cout<<dist[n];
}

Bleeman—ford算法：

复杂度的是O（n^2），相比与floyd算法，该算法主要是找相邻节点,每一轮操作会找到一个最短路径的点，由于有n个点，所以需要进行n次，然后每次需要遍历所有的边。

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
int INF=0x3f3f3f3f;
const int N=20010;
int t[N],dist[N];
struct edge{
	int a;
	int b;
	int c;
}e[N];
signed main(){
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;++i) cin>>t[i];
	for (int i=0;i<m;++i){
		int a,b,c;
		cin>>a>>b>>c;
		e[i].a=a,e[i].b=b,e[i].c=c;
		e[i+m].a=b,e[i+m].b=a,e[i+m].c=c;
	}
	memset(dist,INF,sizeof(dist));
	dist[1]=0;
	for (int k=1;k<=n;++k){	
		for (int i=0;i<2*m;++i){	//双向的 
			int u=e[i].a,v=e[i].b;
			int res=t[v];
			if (v==n)res=0;
			dist[v]=min(dist[v],dist[u]+res+e[i].c);	
		}
	}
	cout<<dist[n];
}

SPFA算法：算法复杂度和Dijkstra一样，但是在最坏的情况下会达到O（n^2）是Bleeman—ford的优化，只更新上一轮有变化的点，不更新所有的点

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f
const int N=20010;
int n,m;
int t[N],dist[N];
struct edge{
	int to;
	int w;
	edge(int a,int b) {
		to=a;
		w=b;
	}	
};
vector<edge>e[N];
int inq[N];	//判断是否在队列内 
void spfa(){
	memset(dist,INF,sizeof(dist));
	dist[1]=0;
	queue<int>q;	//队列内存放的是节点号 
	q.push(1);
	inq[1]=1;
	while (!q.empty()){
		int u=q.front(); q.pop();
		inq[u]=0;
		for (int i=0;i<e[u].size();++i){
			int v=e[u][i].to;
			int w=e[u][i].w;
			int res=t[v];
			if (v==n) res=0;
			if (dist[v]>res+dist[u]+w){		//只处理更新的节点 
				dist[v] =dist[u]+w+res;
				if (!inq[v]){
				inq[v]=1;
				q.push(v);
				}
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for (int i=1;i<=n;++i) cin>>t[i];
	for (int i=0;i<m;++i){
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back(edge(b,c));
		e[b].push_back(edge(a,c));
	}
	spfa();
	cout<<dist[n];
}

最小生成树：

最小生成树https://www.luogu.com.cn/problem/P3366

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 �,�N,M，表示该图共有 �N 个结点和 �M 条无向边。

接下来 �M 行每行包含三个整数 ��,��,��Xi​,Yi​,Zi​，表示有一条长度为 ��Zi​ 的无向边连接结点 ��,��Xi​,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1复制

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1复制

7

说明/提示

数据规模：

对于 20%20% 的数据，�≤5N≤5，�≤20M≤20。

对于 40%40% 的数据，�≤50N≤50，�≤2500M≤2500。

对于 70%70% 的数据，�≤500N≤500，�≤104M≤104。

对于 100%100% 的数据：1≤�≤50001≤N≤5000，1≤�≤2×1051≤M≤2×105，1≤��≤1041≤Zi​≤104。

样例解释：

所以最小生成树的总边权为 2+2+3=72+2+3=7。

Prim算法和Kruskal算法的异同

同：都是利用贪心的方式

异：

Prim算法原理：“最小的邻居一定在树上”，从任意一个点u开始，把距离最近的v加入最小生成树中，下一步把距离{u，v}最近的w加入到树中，并且在生成的过程中保证不会生成环路，直到所有的点都在树上

代码与Dijkstra类似

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f

const int N=4e5+5;
struct edge{
	int to;
	int w;
	edge(int a,int b){
		to=a;
		w=b;
	}
};
vector<edge>e[N];
int n,m,ans;
struct node{
	int id;
	int n_dis;	//区别在于Dijkstra这里存的是该节点到起点的最短距离，而Prim中存的是边长(该节点与其他邻居节点的最短边长) 
	node(int a,int b): id(a),n_dis(b){}
	bool operator < (const node &a)const{
		return n_dis>a.n_dis;
	}
};
priority_queue<node>q;
bool done[N];
int dis[N];
void prim(){
	for (int i=1;i<=n;++i){
		done[i]=false;
		dis[i]=INF;
	}
	dis[1]=0;
	q.push(node(1,dis[1]));
	while (!q.empty()){
		node p=q.top(); q.pop();
		if (done[p.id]) continue;
		done[p.id]=true;
		ans+=dis[p.id];
		for (int i=0;i<e[p.id].size();++i){
			int  v=e[p.id][i].to;
			int  w=e[p.id][i].w;
			if (done[v]) continue;
			if (dis[v]> w){
				dis[v]=w;
				q.push(node(v,w));
			}
		}
	}
	for (int i=1;i<=n;++i){
		if (!done[i]){
			cout<<"orz";
			return;
		}
	}
	cout<<ans;
	return ;
}


signed main(){
	cin>>n>>m;
	for (int i=0;i<m;++i){
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back(edge(b,c));
		e[b].push_back(edge(a,c));
	}
	prim();
}

Kruskal算法原理：

“最短的边一定在最小生成树上”，从最短的边开始操作，以此加到树中。

算法步骤：先对所有的节点关系进行排序，然后依次把最小的边放到最小生成树中，其中对于是否成环（连通性问题）的判定，可以用并查集实现

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f

const int N=4e5+5;
int f[N]; 
struct edge{
	int from;
	int to;
	int dis;
};
edge e[N];
bool cmp(const edge& a,const edge& b){
	return a.dis<b.dis;
}
int find(int x){
	if (f[x]==x){
		return x;
	}else {
		f[x]=find(f[x]);
		return f[x];
	}
}
void unionn(int i,int j){
	f[find(i)]=find(j);
}
int n,m,ans,cnt;

void Kruskal(){
	for (int i=1;i<=n;++i){
		f[i]=i;
	}
	sort(e+1,e+1+m,cmp);	//排序 
	for (int i=1;i<=m;++i){	//开始放边 
		if (find(e[i].from)!=find(e[i].to)){	//如果不会构成环 
			cnt++;	//节点就放到树上 
			ans+=e[i].dis;
			unionn(find(e[i].from),find(e[i].to));	//合并两个节点 
		}
		if (cnt==n-1)break;
	}
	if (cnt!=n-1) cout<<"orz";
	else if (cnt==n-1) cout<<ans;
}
signed main(){
	cin>>n>>m;
	for (int i=1;i<=m;++i){
		cin>>e[i].from>>e[i].to>>e[i].dis;
	}
	Kruskal();
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/386072.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

MySQL：常用指令

MySQL：常用指令

MySQL官网 一、在Windows 系统 cmd窗口里执行的命令 启动:net start MySQL停止:net stop MySQL卸载:sc delete MySQL 二、在macOS系统终端里执行的命令 启动&#xff1a;mysql.server start停止&#xff1a;mysql.server stop重启&#xff1a;mysql.server restart 三、执行帮…
阅读更多...
多尺度神经网络新一代创新！精度与速度完美平衡，实现多领域应用落地

多尺度神经网络新一代创新！精度与速度完美平衡，实现多领域应用落地

多尺度神经网络的设计通常基于对频率原则的理解&#xff0c;目的是为了解决高频成分学习慢的问题。这些网络通过特殊设计&#xff0c;比如给高频成分加更多的权重或者将高频成分平移到低频&#xff0c;来提高学习效率。 为了满足在不同层次上理解和处理数据的需求&#xff0c;…
阅读更多...
JS游戏项目合集【附源码】

JS游戏项目合集【附源码】

文章目录 一&#xff1a;迷宫小游戏二&#xff1a;俄罗斯方块三&#xff1a;压扁小鸟 一&#xff1a;迷宫小游戏 【迷宫游戏】是一款基于HTML5技术开发的游戏&#xff0c;玩法简单。玩家需要在一个迷宫中找到出口并成功逃脱&#xff0c;本项目还有自动寻路&#xff08;Track&a…
阅读更多...
【开源】JAVA+Vue.js实现城市桥梁道路管理系统

【开源】JAVA+Vue.js实现城市桥梁道路管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 查询城市桥梁4.2 新增城市桥梁4.3 编辑城市桥梁4.4 删除城市桥梁4.5 查询单个城市桥梁 五、免责说明 一、摘要 1.1 项目介绍 基于VueSpringBootMySQL的城市桥梁道路管理系统&#xff0c;支持…
阅读更多...
Netty应用(九) 之 编解码器概念 Netty常见的编解码器

Netty应用(九) 之 编解码器概念 Netty常见的编解码器

目录 22.编解码器 22.1 编解码的概念 22.2 netty中的编解码 22.3 序列化 23.编解码器在使用过程中的两部分核心内容 23.1 序列化协议&#xff08;编码格式&#xff09;&#xff08;传输数据的格式&#xff09; 23.1.1 Java默认的序列化与反序列化 23.1.2 XML的序列化与反…
阅读更多...
比特币突破5万美元，2年来首次

比特币突破5万美元，2年来首次

作者&#xff1a;秦晋 2月13日凌晨&#xff0c;时隔两年&#xff0c;比特币首次突破50000美元关口。最高触及50363美元、24小时涨幅3.53%。创下2021年12月以来的新高。 据《财富》报道&#xff0c;本次上涨得益于三方面&#xff0c;首先是比特币ETF资金流入&#xff0c;比特币E…
阅读更多...
docker 2：安装

docker 2：安装

docker 2&#xff1a;安装 ‍ ubuntu 安装 docker sudo apt install docker.io‍ 把当前用户放进 docker 用户组&#xff0c;避免每次运行 docker 命都要使用 sudo​ 或者 root​ 权限。 sudo usermod -aG docker $USER​id $USER ​看到用户已加入 docker 组 ​​ ‍ …
阅读更多...
单例模式 C++

单例模式 C++

6 种 单例 的手写&#xff0c;都是懒汉&#xff08;饿汉代码在 “懒汉 / 饿汉的区别”&#xff09; 目录 ✊前言 &#x1f33c;GPT解析 &#x1f33c;概念解析 RAII 懒汉 / 饿汉的区别 特点 举例 单例 -- 伪代码 适用场景 单例 -- 实现方式 优缺点 &#x1f382;手…
阅读更多...
JavaScript 的ArrayBuffer 和二进制数组

JavaScript 的ArrayBuffer 和二进制数组

&#x1f9d1;‍&#x1f393; 个人主页&#xff1a;《爱蹦跶的大A阿》 &#x1f525;当前正在更新专栏&#xff1a;《VUE》 、《JavaScript保姆级教程》、《krpano》、《krpano中文文档》 ​ ​ ✨ 前言 ​ ✨ 正文 简介 在 JavaScript 中&#xff0c;ArrayBuffer 对象代…
阅读更多...
Java学习-常用API-新增时间

Java学习-常用API-新增时间

1.学习JDK8新增时间的原因&#xff1f; 2.JDK8新增了那些时间&#xff1f; 代替calendar的 localDate localTime localDateTime 常用APi及代码示例&#xff1a; ZoneIdZonedDateTime 常用方法 代码示例&#xff1a; 代替Date的 Instant常见方法及其代码示例&#xff1a; 注…
阅读更多...
GEE：CART（Classification and Regression Trees）回归教程（样本点、特征添加、训练、精度、参数优化）

GEE：CART（Classification and Regression Trees）回归教程（样本点、特征添加、训练、精度、参数优化）

作者：CSDN @ _养乐多_ 对于分类问题，这个输出通常是一个类别标签 ，而对于回归问题，输出通常是一个连续的数值。回归可以应用于多种场景，包括预测土壤PH值、土壤有机碳、土壤水分、碳密度、生物量、气温、海冰厚度、不透水面积百分比、植被覆盖度等。 本文将介绍在Google…
阅读更多...
Vue3快速上手（三）Composition组合式API及setup用法

Vue3快速上手（三）Composition组合式API及setup用法

一、Vue2的API风格 Vue2的API风格是Options API,也叫配置式API。一个功能的数据&#xff0c;交互&#xff0c;计算&#xff0c;监听等都是分别配置在data, methods&#xff0c;computed, watch等模块里的。如下&#xff1a; <template><div class"person"…
阅读更多...
Imgui(1) | 基于imgui-SFML改进自由落体小球

Imgui(1) | 基于imgui-SFML改进自由落体小球

Imgui(1) | 基于imgui-SFML改进自由落体小球 0. 简介 使用 SFML 做2D图形渲染的同时&#xff0c;还想添加一个按钮之类的 GUI Widget, 需要用 Dear Imgui。由于 Imgui 对于2D图形渲染并没有提供类似 SFML 的 API, 结合它们两个使用是一个比较好的方法, 找到了 imgui-SFML 这个…
阅读更多...
阿里云服务器公网带宽收费价格表_2024更新报价

阿里云服务器公网带宽收费价格表_2024更新报价

阿里云服务器公网带宽怎么收费&#xff1f;北京地域服务器按固定带宽计费一个月23元/M&#xff0c;按使用流量计费0.8元/GB&#xff0c;云服务器地域不同实际带宽价格也不同&#xff0c;阿里云服务器网aliyunfuwuqi.com分享不同带宽计费模式下带宽收费价格表&#xff1a; 公网…
阅读更多...
Android---QUMI实现沉浸式状态栏

Android---QUMI实现沉浸式状态栏

沉浸式状态栏是指将 App 的状态栏与应用界面进行融合&#xff0c;使得应用界面能够占据整个屏幕的控件&#xff0c;从而提供更加沉浸式的用户体验。通过使用沉浸式状态栏&#xff0c;应用界面可以延伸到状态栏的区域&#xff0c;使得应用界面的内容更加丰富&#xff0c;同时也能…
阅读更多...
【开源】SpringBoot框架开发校园疫情防控管理系统

【开源】SpringBoot框架开发校园疫情防控管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 学生2.2 老师2.3 学校管理部门 三、系统展示四、核心代码4.1 新增健康情况上报4.2 查询健康咨询4.3 新增离返校申请4.4 查询防疫物资4.5 查询防控宣传数据 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBoot…
阅读更多...
web3知识体系汇总

web3知识体系汇总

web3.0知识体系 1.行业发展 2. web3的特点&#xff1a; 1、统一身份认证系统 2、数据确权与授权 3、隐私保护与抗审查 4、去中心化运行 Web3.0思维技术思维✖金融思维✖社群思维✖产业思维”&#xff0c;才能从容理解未来Web3.0时代的大趋势。 3.技术栈 Web3.jsSolidit…
阅读更多...
【大数据】Flink on Kubernetes 原理剖析

【大数据】Flink on Kubernetes 原理剖析

Flink on Kubernetes 原理剖析 1.基本概念2.架构图3.核心概念4.架构5.JobManager6.TaskManager7.交互8.实践8.1 Session Cluster8.2 Job Cluster 9.问题解答 Kubernetes 是 Google 开源的 容器集群管理系统&#xff0c;其提供应用部署、维护、扩展机制等功能&#xff0c;利用 K…
阅读更多...
深入理解梯度加权类激活热图（Grad-CAM）

深入理解梯度加权类激活热图（Grad-CAM）

深入理解梯度加权类激活热图&#xff08;Grad-CAM&#xff09; 项目背景与意义 在深度学习领域&#xff0c;模型的预测能力往往是黑盒子&#xff0c;难以解释。梯度加权类激活热图&#xff08;Grad-CAM&#xff09;作为一种可解释性技术&#xff0c;能够帮助模型开发者更好地…
阅读更多...
js中事件循环的详解

js中事件循环的详解

文章目录 一、是什么二、宏任务与微任务微任务宏任务 三、async与awaitasyncawait 四、流程分析 一、是什么 首先&#xff0c;JavaScript是一门单线程的语言&#xff0c;意味着同一时间内只能做一件事&#xff0c;但是这并不意味着单线程就是阻塞&#xff0c;而实现单线程非阻…
阅读更多...
最新文章

Copyright @ 2022~2023