第一阶段复习

目录

• 最短路部分
  • 最小环
  • 传递闭包
  • Dij证明
  • 反图
  • 负环
  • 最短路计数
  • 次短路
  • 分层图的几个典例
  • 最短路结合二分

最短路部分

最小环

一些细节：枚举最小环是依据还没有更新经过k的最短路，所以要写在更新经过k的最短路之前。要判断是否存在路径。ijk三指针需要i与k、j与k相连。

传递闭包

f[i][j] |= f[i][k] & f[k][j];

注意是有向图

Dij证明

命题：在取出最短路长度最小的节点u的时候，u的最短路已经被确定，即D(u)=dis(u)
证明：设u是算法中第一个在加入S集合时不满足D(u)=dis(u)的点。（u的存在性略）。一定存在一条路径s→x−y→u，其中y是路径上第一个属于T集合的点。而x和y直接相连，显然x∈S。
因为D(x)=dis(x)，所以（x，y）会被松弛，于是加入u的时候，一定有，D(y)=dis(y)
因为边权为正，所以D(y)≤D(u)，从而dis(y)≤D(y)≤D(u)≤dis(u)。但因为u被取出，所以dis(u)≤dis(y)，故D(u)=dis(u)，与假设矛盾。命题得证。

反图

负环

例题：拉近距离

最短路计数

方法：因为不涉及权值，所以单纯bfs就好。自环不会影响结果，因为如果经过自环，一定比不经过自环要长，所以输入判自环。重边会影响结果，但是一样计入即可（可不可以用乘法什么的优化）。在遇到一个没访问过的点时，一定是最短路，更新即可，该点的计数+=前驱的计数；若遇到访问过的点，且该点最短路长度大于前驱最短路长度（其实这两个长度必定只差1），则依然更新，其他情况都不是最短路，不更新。这题做完了。

次短路

例题：[USACO06NOV]Roadblocks G

• 首先想到在最短路算法的过程中计算次短路。进而想到开两个数组，一个是dis1用来存最短路，一个是dis2用来存次短路。
• 更新最/次短路是最重要的一点。
• 对于u向v的更新：（定义折线长度为u点最短路加(u,v)边权）
• 判断1：如果dis1[v]可以更新，则更新dis1[v] 。（这里可以加一句，让dis2[v]等于先前的dis1[v] ）
• 判断2：如果dis1[v]不能更新（这不代表dis2[v]不能更新）。那么如果折线长度小于dis2[v]，而且折线长度大于dis1[v]（这个dis1[v]并没有被更新，注意这里的逻辑），则更新dis2[v]为折线长度。
• 判断3：注意到判断2中更新dis2[v]的是最短路的折线长度，这一定比次短路的折线长度更优，所以判断2若不成立，那么才考虑，用次短路的折线长度更新。换个角度理解，这个算法其实是两次松弛，判断2保证了严格小于最短路的次短路。
• 对于三个判断，有一个成立，就要入队。因为更新势必造成对之后的影响，就要入队。而且从if，else if的角度也很好理解。
• 这里可以发现，判断123是转折的，可以用else-if连接，比方说，判断2成立，判断3就一定不成立。
• 好在该题可以一条边重复走。

分层图的几个典例

最短路结合二分

例题：通往奥格瑞玛的道路

边权是扣的血量。点权是要花的路费。

那肯定是最短路和边权有关。

二分最小花费，每次跑一次最短路。

单调性：如果