这一章一共7道题,算起来从第一道题到做完一共快三周了。在家实在是堕落,尤其是上知乎看了许多大神刻苦的训练记录更觉得再不加把劲就太对不起自己了。本来只是想小结重温一下Dijkstra\SPFA\Floyd这三个算法,但是LYD上的题都是经典且比较难的题目,所以还是不拖拉,尽量把板子和坑点就总结在这里。之后争取在一个月内把图论专题训练完成总结。(此处立下Flag)。
Dijkstra
由于SPFA的复杂度O(nm)并不算十分优秀且在比赛中有可能被一些特殊数据卡掉,dijkstra是一个在复杂度和稳定性都十分优秀的图论算法,所以熟练掌握十分重要。
dijkstra是一种单源最短路径算法,时间复杂度上限为O(n^2),在实际应用中较为稳定;加上堆优化之后更是具有O(mlogn)的时间复杂度,在稠密图中有不俗的表现。
算法思想
Dijkstra算法基于贪心的思想,它只适用于非负权的图.当边长z均是非负数时,全局最小值不可能再被其他节点更新.所以第二步选出的节点x必然满足dis[x]是起点到节点x的最短路径.当不断地选择全局最小值进行标记和扩展,最终可得到起点1到每个节点的最短路径长度.
算法实现
1.初始化dis[1] = 0,其余节点初始化为无穷大;
2.遍历节点,找到一个未标记的,dis最小的节点x然后标记;
3.扫描x的所有出边,若dis[y] > dis[x] + z,则更新dis[y];
4.重复2~3,直到所有节点均被标记;
PS:遇到负权图也是可以使用Dij的,具体来说就是依照负权建立一个反向图进行计算,具体见下面的例题.
算法模板
邻接矩阵存图
1 | int mp[N][N], dis[N], n, m; |
链表存图(使用二叉堆维护dis数组)
1 | int head[N], ver[M], edge[M], nex[M], dis[N]; |
SPFA
相比较Dijkstra,SPFA的优势是可以更容易的处理有负权的图.
算法思想
给定一张有向图,若对于图中任意一条边(x,y,z),均满足dis[y] ≤ dis[x] + z,则称该边满足三角形不等式,此时dis数组就是所求最短路.
基于迭代思想的Bellman-Ford算法
1.遍历所有的边(x,y,z),若dis[y] > dis[x] + z,则更新dis[y]的最小值;
2.重复上述步骤,直到没有更新的节点;
队列优化的Bellman-Ford算法(SPFA)
1.建立一个队列,最初队列中只含有起点1;
2.取出头节点x,遍历他的所有出边(x,y,z),若dis[y] > dis[x] + z,更新dis[y]的最小值.同时若y不在队列中,将y加入队列中;
3.重复1~2,直到队列为空;
在任意时刻,该算法的队列中都保存了待扩展的节点,每次入队相当于完成一次dis数组的更新操作,使其满足三角形不等式.一个节点可能会入队出队多次,最终所有的节点收敛到全部满足三角不等式.使用队列避免了Bellman-Ford中对不需要的节点进行冗余扫描,在稀疏图上运行效率较高,复杂度为O(km)级别,k为较小的常数.在稠密图或经过特殊构造的图上可能退化为O(nm)
使用双端队列进行优化可以通过一些特殊样例
算法模板
1 | int head[N], ver[M], edge[M], nex[M], dis[N]; |
Floyd
使用Floyd算法可以在O(n^3^)的时间完成求解任意两个节点之间的最短路.Floyd算法的程序实现非常简单.
要理解Floyd的本质是DP.D[k,i,j]表示经过若干不超过k的节点从i到j的最短长度.该问题可以划分为两个子问题:经过编号不超过k-1的节点从i到j和从i先到k再到j.k是阶段,所以必须置于外层的循环中.
算法模板
1 | int dis[N][N], n, m; |
传递闭包问题
在一类具有关系传递性的图中,通过推导可以得出更多元素之间的二元关系.其中dis[i][j]表示i与j有关系,0表示没关系.使用floyd可以很好的得到全图的二元关系.
核心代码
1 | for1(k, n) for1(i, n) for1(j, n) { |
POJ3662 Telephone Lines
题意
图上有N个节点,P条无向边连接Ai和Bi.要求找出一条从1~N的路径,使路径上第K+1大的边权尽量小.
思路:最短路 + 二分
这道题的核心是使第k位置的权值尽量小,且答案具有单调性.这样的类似问题应该想到二分.L在1~1e6之间,我们就可以在这个区间枚举第k+1的权值判断是否比他大的边不多于k个.这里dis不存储最短路径长,而是记录在路径中的大小顺序.
代码
1 | int n, p, k, tot; |
思路2:最短路 + dp
仿照dp的思想,用dis[x][p]表示从1号节点到达基站x,途中指定p条线路免费时,经过的路径上最贵的电缆的花费最小是多少(选择一条从1->x的路径,使路径上第p+1大的边尽量小).若有一条x->y的路径权值为z,则使用max(dis[x][p], z)更新dis[y][p]的最小值(也就是这条边不使用优惠);用dis[x][p]更新dis[y][p+1]的最小值(即当前边使用优惠);
代码
1 | int n, p, k, tot, ans; |
NOIP2009 最优贸易
题意
给出n个节点和连接他们的m条道路,其中有单向和双向两种道路.目标是在从1~n的道路上先后选取两个不同的节点p和q,使得后者q减去前者p最大.
思路1:两次相反的最短路
可以将双向道路看作两条相反方向的单向道路,然后建立相反的一张图,分别从1n和从n1进行两次最短路.dis[x]分别表示从起点到节点x最小的进货价和最大的出货价.最后,枚举每个节点x,用dis1-dis2更新答案即可.
代码
1 | int n, m, tot, ans; |
思路2:分层图SPFA
分析题目可以发现,阿龙在1~n的旅程中共有三种状态:
1.持币观望寻找合适的地方下手抄底,此时金钱-0;
2.到了某地决定下手,购入商品,此时金钱-val[i];
3.购入商品后又到了某地决定出手,此时金钱+val[i];
根据这三种状态我们可以建立三层图,关系为:
1.如果在第一层,那么可以选择进入第二层(花钱)或者不进入直到终点n(不赚不赔);
2.如果在第二层,那么必须寻找赚钱的地方出手(否则赔钱)进入第三层;
3.如果在第三层,更新答案即可;
代码
1 | struct node { |
思路3:搜索+dp
见代码
1 | // 最小成本、参数值、最大收益 |
P3008 Roads and Planes
题意
给出一张具有T个节点的图,图中各点由双向道路和单向道路分别连接,其中单项道路的权值可能为负.现在要求找出一条从起点到各节点所需的最便宜的方案.
思路:建立DAG使用拓扑排序+堆优化的dijkstra
本题存在负边权,不能直接使用Dij,但是如果使用SPFA会被卡掉.所以分析题意可以发现单向边组成的图不构成环,如果仅仅把双向边加入图中可以发现形成的时若干个连通块.若把每一个人连通块看作点,再添加单向边,会得到一张有向无环图DAG,再DAG中不论权值正负均可以通过拓扑排序处理,再连通块内使用堆优化的Dij快速计算块内的最短路.
代码
1 | struct node { |
POJ1094 Sorting It All Out
题意
给定n个变量和m个不等式描述n个变量之间的大小关系,根据m个不等式判断n个元素的大小关系,有三种结果:
1、可以确定全部元素的大小关系,并从小到大排列;
2、不等式之间的逻辑关系有矛盾;
3、所给条件不足以判断所有元素之间的关系;
最后还要求出只需几个不等式即可得出结果。
思路1:Floyd传递闭包+拓扑排序
1 | int n, m, mp[N][N], deg[N], cnt; |
思路2:纯拓扑排序
1 | int n, m, mp[N][N], deg[N]; |
POJ1734 无向图最小环问题
题意
给定一张无向图,求图中一个至少包含3个点的环,环上的点不重复且权值之和最小.
思路:Floyd算法k的本质
当外层循环开始时,dis[i][j]保存的是经过编号不超过k-1的点从i~j的最短长度,所以min(dis[i][j] + mp[j][k] + mp[k][i])就相当于枚举了环上和k相邻的两个点.
代码
1 | int mp[N][N], dis[N][N], mid[N][N]; |
POJ3613 Floyd+矩阵快速幂
这道题毒了好久才有点懂..
题意
给定一张不超过100条边构成的无向图,点的编号为1~1000,求从起点S到终点E恰好经过N条边的最短路.
代码
1 | int n, m, s, e, tot; |