首页 > 其他分享 >浅谈图论

浅谈图论

时间:2023-07-03 13:33:15浏览次数:42  
标签:图论 松弛 浅谈 短路 枚举 考虑

  • 多源最短路算法(Floyd)

    说到最短路,就不得不提到松弛。
    所谓松弛,就是当存在\(w_{u,v}>w_{u,k}+w_{k,v}\)时,令\(w_{u,v}=w_{u,k}+w_{k,v}\)
    一般来说,松弛操作后,我们会用松弛后的边不断松弛其他边,而这,就是大部分最短路算法的思路。
    思考一下,若用DP的思想考虑,那么我们易设出状态\(f_{i,j}\)表示从\(i\)到\(j\)的最短路,但是这个状态显然具有后效性,因为我们显然无法一遍就能转移出\(f_{i,j}\)的正确结果,需要不断对其他边进行松弛操作才能得出最后答案,所以同为\(f_{i,j}\)的值在不同阶段会有不同的值。
    那么考虑加一维表示松弛阶段,则最显然表示松弛阶段的方式是边,然而边太多且一个边能松弛其他边的数量及其有限,故考虑点。
    则设\(f_{k,i,j}\)为只考虑前\(k\)个点时,从\(i\)到\(j\)的最短路。
    那么可以推出转移式\(f_{k,u,v} = min(f_{k,u,v},f_{k-1,u,k}+f_{k-1,k,v})\)
    不断枚举\(k\),然后枚举所有\(i,j\),用\(k\)这个端点去更新它们。
    观察到\(f_{k,i,j}\)的值只与\(f_{k-1,i,j}\)有关,故可以用滚动数组压成二维。
    代码如下:
for (int k = 1; k <= n; ++k) 
        for (int u = 1; u <= n; ++u)
            for (int v = 1; v <= n; ++v)  f[u][v] = min(f[u][v], f[u][k] + f[k][v]); `

标签:图论,松弛,浅谈,短路,枚举,考虑
From: https://www.cnblogs.com/Kazdale/p/17518758.html

相关文章

  • 浅谈线性规划
    以前学了很多次都没学明白,今天再来看看。本文不会涉及单纯形法的知识点讲解,大部分题目侧重于线性规划对偶。同样本文不会涉及相关知识点的证明,或是线性规划解的整数性说明,毕竟这只是一个总结性的文章。拉格朗日对偶部分没学会,暂鸽。线性规划标准型对于任意线性规划,容易通过......
  • 图论:图的概念、存储和遍历 学习笔记
    图论图的概念从数据结构的角度看,图可以看作一个多对多的数据存储结构。而结合图论算法,图就可以成为很多问题的载体。图论是数据结构与算法结合的产物。OIWiki上给出的图相关概念比较全面,但是因为OI是民科各个地方的一些定义都不太一样,所以作大概了解即可。图的存储图的存......
  • 浅谈线性基
    前言线性基是一种处理异或问题的利器,拥有优秀的时间复杂度基本性质概念定义:给定数集\(S\),以异或运算张成的数集与\(S\)相同的极大线性无关集,称为原数集的一个线性基。通俗地说,线性基是一个数的集合。每个序列都拥有至少一个线性基。取线性基中若干个数异或起来可以得到原......
  • 图论2
    内容来自紫书、2019wannaflycamp、进阶指南、算法导论,可能根本看不完,可能这一切都没有意义。图论以前学算法的时候,很少关心算法正确性的证明,和传统的理科课程如高数课这一类课差得太远了。参加编程竞赛时每一份代码就像黑盒,没有方向感,看起来就像另外一种应试。图的存储略广......
  • 浅谈一下c#多线程编程
    概念线程:线程是操作系统能够进行运算调度的最小单位,被包含在进程之中,是进程中的实际运作单位。同步:一定要等任务执行完了,得到结果,才执行下一个任务。如果程序执行耗时操作时会阻塞线程。应用场景UI与I/O:UI发出I/O操作,I/O操作是费时任务计算密集型工作(CPU-boun......
  • 浅谈PCBA板机械加工分类
    印制板的机械加工主要应用于印制板坯料的下料(俗称开料)、孔加工和外形加工,是印制板整个工艺程序中的重要步骤。由于印制板的孔和外形加工质量都直接影响印制板的机械装配性能和电气连接性能,尤其是印制板上各种用途的孔(元件安装孔、导通孔、安装孔、定位孔、检测孔等)加工质量还会影......
  • 浅谈装配式建筑的抗震性能到底好不好?
    前言根据国家标准《装配式混凝土建筑技术标准》GB/T51231-2016、《装配式混凝土结构技术规程》JGJ1-2014的相关内容,目前我国的装配式建筑结构的抗震性能基本等同于现浇结构的抗震性能。而实际上,由于预制构件的标准化生产,其实际的混凝土性能指标是优于现场浇筑的混凝土的,因此,在所有......
  • 浅谈SpringSecurity与CVE-2023-22602
    一、前言  前段时间Apache报告了CVE-2023-22602,由于1.11.0及之前版本的Shiro只兼容Spring的ant-style路径匹配模式(patternmatching),且2.6及之后版本的SpringBoot将SpringMVC处理请求的路径匹配模式从AntPathMatcher更改为了PathPatternParser,当1.11.0及之前版......
  • 牛客图论 (第一章)
    F棋盘覆盖#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=105,M=N*N*4,ID=N*N+N;intn,m;inthead[ID],ver[M],nxt[M],tot;boolban[N][N];intdx[]={1,-1,0,0},dy[]={0,0,1,-1};intmatch[ID];boolv[ID];......
  • 浅谈单调队列优化DP
    对于形如\[f_i=\max(f_{L≤j≤R}+w_i)\]的状态转移方程,也就是转移来自之前某个定长区间的最值,我们可以使用单调队列来维护区间最值,从而优化时间复杂度。烽火传递我们看到题目可以想到用\(f_i\)表示考虑到\(i\)这个烽火台,点第\(i\)个的合法方案中的最小代价那么可以想到......