最短路
作者:
做ac梦w
,
2022-07-04 15:34:19
,
所有人可见
,
阅读 247
图论
最短路:
1.热浪 单源最短路模板 朴素dij即可
2.信使 求从起点1出发到n个信站全部走过的最短时间 跑单源最短路 求max(dis[1,i]) 1<=i<=n;
3.黄油 求所有奶牛到所有点的最小距离和 枚举所有牧场作为终点 跑n次dij
4.最小花费 求a转账给b到账100元 a的最小花费 设两条路距离为1-利率 求一条乘积最大的线路 保证损失最小
5.最优乘车 每条巴士线路之间每两个点连一条边 跑最短路
6.昂贵的聘礼 建立虚拟源点连每一个物品 终点为女儿 等级制度(等级差) 每次只在规定范围内的等级制度内交易
7.新年好 问拜访五个亲戚abcde的最短路 以此以abcde和1为起点 求出到每个点的最小距离 dfs枚举所有顺序可能 求最小的路线长度
8.通信线路 如果1-n经过k条边及以下 花费为0 如果经过k以上 花费为第k+1大的边
二分枚举答案x 跑dij <=x的贡献为0 >x的贡献为1 看最短路dis[n]是否<=k dis[n]<=k则 k满足条件尝试更小
如果dis[n]>k k不满足条件 k要变大
9.道路与航线 航线边权为负 单向边 道路边权为正 双向边 求单源最短路
航线满足拓扑序 道路相互能去的点组成连通块 按拓扑序在在块内跑dij求最小值 如果有非块内的点 跟新距离不入优先队列 入度-- 如果入度为0 入拓扑排序的序列
10.最优贸易 dmin[i]表示在到i点前买入的最小值 dmax[i]表示在到i点后卖出的最大值
枚举i求dmax[i]-dmin[i]的最大值 由于dmin[i]不满足拓扑序 不是递增序列 因此要用spfa
11.选择最佳线路:建立虚拟源点即可
12.拯救大兵瑞恩 分层图 加多一维状态state表示拥有的钥匙数 bfs爆搜
13.最短路计数 cnt[i]表示到i点最短路条数 找到一条更短的 直接覆盖 找到相同距离的 加上即可
14.观光 求次短路 分层图 加多一维表示次短路和最短路 跑dij。
floyd:
牛的旅行: 先算出有直接相连的欧几里得距离 再跑floyd求每两个点距离
求maxi 每个点到点i的最短距离取max maxn为所有围栏中最大的直径
枚举不连通的两个点 连边求maxi+maxj+get(i,j)的最小值 再与maxn取max为最小的直径
排序:求传递闭包 A<B看成A-B的边 跑floyd
考虑三种情况 1.d[i][i]=1; 矛盾
2.d[i][j]=0&&d[j][i]=0; 不确定
3.d[i][j]=!d[j][i] 确定
最小环问题:环看成i-j-k-i floyd在k循环刚开始时 d[i][j]记录的是经过1~k-1这些边得到的i~j的最短距离
因此答案恰好为d[i][j]+g[j][k]+g[k][i];
记录路径:pos[i][j]表示i经过k走到j 再递归i~k和k~j即可
牛站 求s到e恰好经过k条边的最短路 把k二进制拆分 如k=38 即求走2条边 4条边 32条边的最短距离
跟快速幂原理一致 考虑迭代 g数组为原来走一条边的数组 g[i][i]!=0 保证一条边
通过g数组倍增迭代算出走n次的最短距离 当k的二进制为1时 答案数组res要和g数组相加
求出此时走res+(2<<k)的最短距离 答案数组res要把res[i][i]为0 保证能更新答案
最小生成树:
局域网:总边数量-最小生成树
繁忙的都市:最小生成树的最大边
联络员:必选边和可选边 先选必选 可选不联通的情况下选
连接格点:n*m的网格两两建边 求最小生成树
%