【图论】最短路的传送问题

这篇具有很好参考价值的文章主要介绍了【图论】最短路的传送问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.分层图问题(单源传送)

(1)题目

P4568 [JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

(2)思路

可知背景就是求最短路问题,但难点是可以使一条路距离缩短至0,那如何更好的利用这个机会呢?

此时我们可以用到分层图,如下:

【图论】最短路的传送问题,图论,图论

即我们可以免费往下传一次,其实也就相当于两点距离为0了,这时终点应该9号节点。

于是建图如下:

			add(u+(j-1)*n,v+j*n,0);
			add(v+(j-1)*n,u+j*n,0);
			add(u+j*n,v+j*n,w);
			add(v+j*n,u+j*n,w);

第一个是从上到下,是使用传送的边

第二个是第一个的逆向

第三个是已经用过一次机会,已经在下面了,所以正常边

第四个是第三个的逆向

	for(int j=1;j<=k;j++){
		add(s+(j-1)*n,s+j*n,0);
	}

这个是特殊情况,起点即终点,一路传送,其实多此一举,但没办法,只怪我们把图分层了。不能在自环到达了。

(3)参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int s,e;
struct Edge{
	int u,v,w,next;
}edge[2500001];
int head[110005],cnt;
void add(int u,int v,int w){
	edge[++cnt]=(Edge){u,v,w,head[u]}; head[u]=cnt;
}
int dis[110005],vis[110005];
struct node{
	int u,w;
	bool operator < (const node &x) const{
		return x.w<w;
	}
};
void dijkstra(){
	priority_queue<node>q;
	memset(dis,0x3f,sizeof(dis));
	q.push((node){s,0});
	dis[s]=0;
	while(!q.empty()){
		node temp=q.top(); q.pop();
		int u=temp.u;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v,w=edge[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push((node){v,dis[v]});
			}
		}
	}
}
int main(){
	cin>>n>>m>>k>>s>>e;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);add(v,u,w);
		for(int j=1;j<=k;j++){
			add(u+(j-1)*n,v+j*n,0);
			add(v+(j-1)*n,u+j*n,0);
			add(u+j*n,v+j*n,w);
			add(v+j*n,u+j*n,w);
		}
	}
	for(int j=1;j<=k;j++){
		add(s+(j-1)*n,s+j*n,0);
	}
	dijkstra();
	cout<<dis[e+k*n];
	return 0;
}

二.多源传送

(1)题目

P6464 [传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

(2)思路

这题虽然是多源,但只有一个传送门,而且数据范围小,只有100,所以直接上floyd算法!

因为我们不知道传送门怎么建立,所以直接暴力枚举就行了。

我们两重遍历,找出门,在两重暴力folyd即可。

Q:folyd不是三重吗?

A:不是已经知道在哪搭桥了吗?

Q:其他不也可以搭桥吗?

A:前面的预处理三重floyd已经处理好了。文章来源地址https://www.toymoban.com/news/detail-658789.html

(3)参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[101][101];
int F[101][101];
inline void back()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			F[i][j]=f[i][j];
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(f,-1,sizeof(f));
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(f[u][v]==-1||f[u][v]>w)	f[u][v]=f[v][u]=w;//建边,防重边(不过数据里没有)
	}
	for(int k=1;k<=n;k++)	
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(f[i][k]!=-1&&f[k][j]!=-1)
					if(f[i][j]==-1||f[i][j]>f[k][j]+f[i][k])
						f[i][j]=f[i][k]+f[k][j];//Floyd
	int ans=2e9;//较大值
	for(int i=1;i<=n;i++)	
		for(int j=1;j<=n;j++)//暴力枚举
		{
			back();//先让F数组还原成f数组
			F[i][j]=F[j][i]=0;//在教学楼 i 和 j 之间建立传送门
			//i点搭桥 
			for(int x=1;x<=n;x++)	
				for(int y=1;y<=n;y++)	
					if(F[x][y]==-1||F[x][y]>F[x][i]+F[i][y])
						F[x][y]=F[x][i]+F[i][y];//Floyd
			//j点搭桥 
			for(int x=1;x<=n;x++)
				for(int y=1;y<=n;y++)	
					if(F[x][y]==-1||F[x][y]>F[x][j]+F[j][y])
						F[x][y]=F[x][j]+F[j][y];//Floyd
			int res=0;
			for(int x=1;x<=n;x++)	
				for(int y=1;y<x;y++)
					res+=F[x][y];
			ans=min(res,ans);
		}
	printf("%d\n",ans);
	return 0;
}

到了这里,关于【图论】最短路的传送问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论 <最短路问题>模板

    有向图 1.邻接矩阵,稠密图 2.邻接表 (常用)单链表,每一个点都有一个单链表 ,插入一般在头的地方插, 图的邻接表的存储方式 树的深度优先遍历 特殊的深度优先搜索,难点是如何实现,一条道走到黑 树的宽度优先遍历 例题:图的层序搜索 拓扑序列(有向图) 例题

    2024年02月14日
    浏览(27)
  • 图论---最短路问题

    单源最短路 n: 点的数量 m: 边的数量 所有边权都是正数 (1)朴素Dijkstra算法 O(n^2) (2)堆优化版的Dijkstra算法 O(mlogn) 存在负权边 (1)Bellmax-Fold O(nm) (让选择不超过k条边的时候使用) (2)SPFA 一般O(m),最坏O(nm) 多源汇最短路 Floyd算法 O(n^3) 每次找到距离起点最近的点,然后用这个点去更新

    2024年02月05日
    浏览(29)
  • 图论与算法(7)最短路径问题

    最短路径问题是指在一个加权图中寻找两个顶点之间的最短路径,其中路径的长度由边的权重确定。 常见的最短路径算法包括: Dijkstra算法 :适用于解决单源最短路径问题,即从一个固定的起点到图中所有其他顶点的最短路径。该算法通过不断选择当前路径上权重最小的顶

    2024年02月06日
    浏览(41)
  • 搜索与图论第六期 最短路问题

    Dijkstra算法是一种著名的图算法,主要用于求解有权图中的单源最短路径问题。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉(Edsger Wybe Dijkstra)在1956年首次提出。Dijkstra算法的核心思想是通过以下步骤逐步构建最短路径树: 初始化:创建一个空白的最短路径字典,其中每

    2024年02月20日
    浏览(42)
  • [数学建模]图论之最短路径问题

    目录 一、引入图论  二、图的基本概念与数据结构 1.基本概念  2.图与网络结构 1.邻接矩阵表示法  2.稀疏矩阵表示法 三、最短路径问题 1、迪杰斯特拉(Dijkstra)算法 2、贝尔曼-福特(Bellman-Ford)算法 3、弗洛伊德(Floyd)算法         图论起源于18世纪,近几十年来,计

    2024年02月06日
    浏览(46)
  • 第三章 搜索与图论(二)——最短路问题

    源点表示起点,汇点表示终点 一些认识: m和 n 2 n^2 n 2 一个级别是稠密图,m和n一个级别是稀疏图 最短路问题不区分有向图与无向图,因为无向图是一种特殊的有向图,能解决有向图的最短路问题,就能解决无向图的最短路问题 起点确定,终点是除起点外的其他点 默认n表示

    2024年02月13日
    浏览(39)
  • 数学建模十大算法04—图论算法(最短路径、最小生成树、最大流问题、二分图)

    一、最短路径问题 从图中的某个顶点出发,到达另一个顶点的 所经过的边的权重之和最小 的一条路径。 1.1 两个指定顶点之间的最短路径 问题如下:给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,求一条最短铁路线。 1.1.1 Dijkstra算法 迪杰斯特拉(D

    2024年02月02日
    浏览(71)
  • 【图论 单源最短路】100276. 最短路径中的边

    单源最短路 图论知识汇总 给你一个 n 个节点的无向带权图,节点编号为 0 到 n - 1 。图中总共有 m 条边,用二维数组 edges 表示,其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。 对于节点 0 为出发点,节点 n - 1 为结束点的所有最短路,你需要返回一个长度

    2024年04月22日
    浏览(34)
  • 图论——最短路径

    Dijkstra’s algorithm(迪杰斯特拉算法)是一种用于解决图中单源最短路径问题的贪婪算法。该算法由荷兰计算机科学家Edsger Dijkstra于1956年提出。它主要用于计算从一个起始顶点到图中所有其他顶点的最短路径。 算法步骤如下: 初始化: 创建一个集合S,用于存储已找到最短路

    2024年02月21日
    浏览(38)
  • 【图论】最短路算法

    不能处理边权为负的情况, 复杂度O(nlogn) 步骤与基本思路 (1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0,存入优先队列heap中 (2)从所有 未被遍历 的点中找到与起点1的 距离dist[i]最小 的点,并将该点标记为已遍历 (3)利用刚刚遍历的这个点

    2024年02月16日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包