NOIP图论详解.pptx

图论·GraphTheory北京大学李煜东PekingUniversity图的存储基本知识图论GraphTheory图的遍历深度优先遍历访问标记避免重复、时间戳(dfn)广度优先遍历循环队列、优先队列边权为01的图上双端队列拓扑排序判定有向无环图(DAG)基本知识图论GraphTheory任意两点间的最短路问题使用动态规划求解？需要定义状态、阶段、决策。以长度为阶段？经过k条边从x到y的最短路F[k,x,y]=Min{F[i,x,z]+F[k-i,z,y]}，O(N^4)倍增优化？经过2^k条边从x到y的最短路F[k,x,y]=Min{F[k-1,x,z]+F[k-1,z,y]}经过=2^k条边从x到y的最短路D[k,x,y]=Min(D[k-1,x,y],F[k,x,y])经过=N条边从x到y的最短路：对N二进制分解，套用矩阵乘法模型这里重新定义运算规则：加法←求Min，乘法←加法。O(N^3logN)其实可以直接套用矩阵乘法模型求邻接矩阵A的N次方？最短路图论GraphTheoryFloyd算法动态规划以”途径点集大小”为阶段？以长度为阶段效率不高，是因为没有充分利用阶段与决策之间的关系决策需要枚举中转点，不妨考虑也以中转点集为阶段F[k,i,j]表示”可以经过标号≤k的点中转时”从i到j的最短路F[0,i,j]=A[i,j]，A为前面定义的邻接矩阵F[k,i,j]=Min{F[k-1,i,k]+F[k-1,k,j]}，O(N^3)k这一维空间可以省略，变成D[i,j]就成为了我们平时常见的Floyd算法由于k是DP的阶段循环，所以k循环必须要放在最外层最短路图论GraphTheoryPOJ3613T个点的无向图，求从S到E经过恰好N条边的最短路T=100，N=1000000使用以长度为阶段的DP算法用倍增or矩阵乘法加速最短路图论GraphTheoryFloyd求最小环(POJ1734)最小环：从一个点出发经过至少一条边回到该点，不能重复经过某条边，距离最短的回路。有向图最小环：令dist[i,i]=+∞，然后floyd求最短路。无向图最小环：在最外层循环开始进行k时，用“i到k、再到j、再经过编号k的节点从j到i”的最短路w(i,k)+w(k,j)+dist[i,j]来更新最小环。最短路图论GraphTheoryMatrix-Tree定理生成树计数图论GraphTheory单源最短路径问题Dijkstra算法堆优化的Dijkstra算法Bellman-Ford算法SPFA(ShortestPathFastAlgorithm)算法SLF优化的SPFA算法最短路图论GraphTheoryDijkstra算法节点分成两组：已经确定最短路、尚未确定最短路不断从第2组中选择路径长度最短的点放入第1组并扩展本质是贪心，只能应用于正权图普通的Dijkstra算法O(N^2)堆优化的Dijkstra算法O(NlogN)~O(MlogN)最短路图论GraphTheorySPFA算法Bellman-Ford算法：对每条边执行更新，迭代N-1次SPFA=队列优化的Bellman-Ford算法本质上还是迭代——每更新一次就考虑入队稀疏图上O(kN)，稠密图上退化到O(N^2)SLF优化：SmallLabelFirst,新入队点与队头比较LLL优化：LargeLabelLast,队头与平均值比较可以应用于负权图最短路图论GraphTheoryTyvj2032/p/2032简单的变形——最短路的状态扩展到二维D[i,j]表示到达第i层手柄在位置j时的最短时间最短路图论GraphTheoryPOJ3463题意：求最短路、次短路及其条数？d[i][0]表示起点到i的最短路权值，f[i][0]表示其条数。d[i][1]表示起点到i的次短路权值，f[i][1]表示其条数。仍然套用Dijkstra或SPFA求最短路的模板，更新的时候分4种情况讨论：d[x][k]+z=d[y][0]，那么f[y][0]+=f[x][k]。d[x][k]+z=d[y][1]，那么f[y][1]+=f[x][k]。d[x][k]+zd[y][0]，那么d[y][1]=d[y][0],f[y][1]=f[y][0], d[y][0]=d[x][k]+z,f[y][0]=f[x][k]。d[y][0]d[x][k]+zd[y][1]，那么d[y][1]=d[x][k]+z,f[y][1]=f[x][k]。最短路图论GraphTheoryPOJ3635题意：有N（1≤N≤1,000）个城市和M（1≤M≤10,000）条道路。加油站都在城市里面，价格不一样；道路的权值就是这条道路要耗多少油。现在你需要计算一下，一架油箱容量为C（1≤C≤100）的车子，从S开到T至少要花多少油