【学习笔记】Floyd的妙用
前言
(floyd)是一个广为人知的多源最短路算法，时间复杂度(O(N^3))。事实上，(floyd)有一些其他的用法。本文旨在介绍这些用法，欢迎补充
1.最短路计数
单纯的最短路计数，事实上也能通过(SPFA)实现。而求两点之间经过某个点的最短路路径数，实现可以用两次(SPFA)。假若时间复杂度允许，亦可用下面介绍的方法，代码较为简单。
这道题是多源最短路，所以用(floyd)实现求最短路。
设(f[i][j])为(i)到(j)最短路长度，(s[i][j])为最短路径数。对于一点(k)，如果(f[i][k]+f[k][j]=f[i][j])，则经过该点的最短路径条数为(s[i][k] imes s[k][j])。
2.经过(k)条边
对于诸如求两点之间经过(k)条边的最短路长度/路径数的问题，用(dij/SPFA)较难实现，这时候可以尝试使用(floyd)。下面通过例题介绍。
P2886 [USACO07NOV]牛继电器Cow Relays
在本题中，用(SPFA)直接求空间会爆，只能考虑使用(floyd)求经过(1le Kle k)条路径的最短路。(k)如此大以至于会(TLE)。于是我们可以通过倍增解决。
BTW，本题也可以通过矩阵快速幂解决，详情请见info___tion的blog
3.最小环
(floyd)可以求无向图和有向图的最小环。
对于在有向图中，求经过第(i)个点的最小环，我们可以把(f[i][i]= infin)，跑一遍(floyd)，则最小环为(f[i][i])。
而在无向图中，方法有些不同。因为不能重复经过某一条边，上述方法为错解。
依照(floyd)的实现方式，在第 (k) 轮循环中，(f_{i,j})记录的是在只经过前 (k) 点的情况下从 (i) 到 (j) 的最短路。
类似的，在第 (k) 轮循环中，用(f_{k,k})记录的是在只经过前 (k) 点的情况下从 (k) 到 (k) 的最短路，即以 (k) 为编号最大的点的最小环的长度。
该环由三部分组成：从 (k) 到 (i) 的一条边，(i) 到 (j) 的多条边, (j) 到 (k) 的一条边。
那么用第 (k-1) 轮循环得出的 (f)，更新(f_{k,k})即可
代码如下
for (int k=1;k<=n;k++)
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (i!=j&&i<=k&&j<=k) f[k][k]=min(f[k][k],e[i][k]+e[k][j]+f[i][j]);
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (i!=j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
而对于上面的例题，我们还需要用叉积判断是否所有点都在边的同一边，再根据实际情况建单向边，详情看大佬题解
4.图的传递闭包
这东西(OI)好像不常考？
那么就咕掉吧。
总结
(floyd)不仅可以求多源最短路，也可以求一些base on最短路的问题。不过由于其时间复杂度较大，需要谨慎使用