温故知新 —— Floyd算法

什么？Floyd？sb O(n ^ 3) 算法早不用了，右上角红叉吧。
我之前虽然也认识过 Floyd 算法的重要性，不过多少也是这么想的。
然而最近三天连续 rand 到了好几道有关的题目，让我彻底重新审视了 Floyd —— 既然能够作为一个重要的算法流传至今，那自有他的重要之处。

Floyd 是一个求解所有点对间的最短路算法，也可能是绝大多数人接触的最早的最短路算法。它适用于无负权边的图，时间复杂度约为 O(n ^ 3) 。因为时间复杂度太高了，所以也是很多人起初都对它有些成见的原因，再加上任意点对间最短路用的又少，会误认为这个算法后期就一无是处了。
众所周知，Floyd 的本质是动态规划。对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是就更新它。正是由于这个动态规划思想的精髓所在，以及一层层更新的特性，使得 Floyd 大有用武之地。
废话不多说了，反正四行的 Floyd 没人不会……

万恶之源那天，我正在 Luogu 愉快地随机跳题，于是就 rand 到了 P2103 道路值守。
很开心，这不就是个最短路计数？正巧前一天就 A 了一道类似的题，很快就敲出来准备 AC 了。结果嘛……
怎么办，蒟蒻 Nanjo_Qi 瞬间就没有思路了，于是只能求助题解。
结果是个用到 Floyd 的题目。

Floyd 的重要特性是：全面枚举，有序更新。

Floyd题：https://www.luogu.org/problemnew/show/P2103。
这个也是：https://www.luogu.org/problemnew/show/P1476。
这个也是：https://www.luogu.org/problemnew/show/P1119。

P2103 道路值守：

利用 Floyd 层层松弛更新，以及循环遍历所有点对的特性，完全无需考虑时间复杂度；
首先求出所有点对间最短路，然后枚举寻找那些可以作为方案数加入的点（另一条与最短路长度相等，或中途汇入最短路的道路，以此形成可行方案），分别在每个汇入点记录，最后累计。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 500 + 10;
int n, m, g[maxn][maxn], dis[maxn][maxn], method[maxn][maxn];

int main(int argc, char const *argv[])
{
  memset(dis, 0x3f, sizeof dis);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    int u = 0, v = 0, w = 0;
    scanf("%d%d%d", &u, &v, &w);
    dis[u][v] = dis[v][u] = g[u][v] = g[v][u] = w;
  }
  for(int i = 1; i <= n; ++i) dis[i][i] = 0;
  for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

  for(int i = 1; i <= n; ++i) {
    int tmp[maxn] = {0};
    for(int j = 1; j <= n; ++j) if( i != j && dis[i][j] != dis[0][0] )
      for(int k = 1; k <= n; ++k) if( g[k][j] )
        if( dis[i][j] == dis[i][k] + g[k][j] ) ++tmp[j];

    for(int j = 1; j <= n; ++j) if( i != j )
      for(int k = 1; k <= n; ++k)
        if( dis[i][j] == dis[i][k] + dis[k][j] ) method[i][j] += tmp[k];
  }

  for(int i = 1; i <= n; ++i)
    for(int j = i + 1; j <= n; ++j)
      printf("%d ", method[i][j]);

  // printf("_______________________________________________
");
  // printf("Process Exited Correctly With A Return Value 0.
");
  // printf("All Rights Reserved By Kimitsu Nanjo In 2018.

");
  return 0;
}

P1476 休息中的小呆：

求 1 到 n + 1 的最长路；
用 Dijkstra 不知道为什么跪在了记录路径上，还是用 Floyd 边枚举边输出。

#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, dis[105][105];

int main(int argc, char const *argv[])
{
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    int u = 1, v = 1, w = 1;
    scanf("%d%d%d", &u, &v, &w);
    dis[u][v] = w;
  }
  for(int k = 1; k <= n + 1; ++k)
    for(int i = 1; i <= n + 1; ++i)
      for(int j = 1; j <= n + 1; ++j)
        if( i != j && j != k && dis[i][k] && dis[k][j] )
          dis[i][j] = max(dis[i][j], dis[i][k] + dis[k][j]);
  printf("%d
", dis[1][n + 1]);
  for(int i = 1; i <= n + 1; ++i)
    if( dis[1][i] + dis[i][n + 1] == dis[1][n + 1] )
      printf("%d ", i);

//   printf("_______________________________________________
");
//   printf("Process Exited Correctly With A Return Value 0.
");
//   printf("All Rights Reserved By Kimitsu Nanjo In 2018.

");
  return 0;
}

P1119 灾后重建：

一两个月前做的题，本质是最短路，那时却完全不知道这个时间限制怎么处理（那时的代码还是如此的丑）；
依然是 Floyd，因为这道题保证修复时间和询问都是是递增的，所以就使 k 作为全局变量，每次 k 只以已经修复完成的村庄进行松弛更新，一旦发现村庄 k 的修复时间大于此时的时间，k 就停止自增，等待下一次询问。

#include<cstdio>
#include<cstring>

int g[210][210], t[210];
int n, m, q, u, v, w, d, k;
inline int min(int a, int b) {
    return a>b?b:a;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    memset(t, 0x3f, sizeof(t));
    for(int i=0; i<n; ++i) {
        scanf("%d", &t[i]);
        g[i][i] = 0;
    }
    for(int i=0; i<m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = g[v][u] = w;
    }
    
    scanf("%d", &q);
    for(int i=0; i<q; ++i) {
        scanf("%d%d%d", &u, &v, &d);
        while( t[k]<=d ) {
            for(int i=0; i<n; ++i) {
                for(int j=0; j<n; ++j) {
                    g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
                }
            }
            ++k;
        }
        if( t[u]>d || t[v]>d || g[u][v]==0x3f3f3f3f ) {
            printf("-1
");
        }
        else {
            printf("%d
", g[u][v]);
        }
    }
    return 0;
}

另外，Floyd 还可以用来求最小环，一个环中的最大结点为 k，与他相连的两个点为 i，j，这个环的最短长度为 g[i][k] + g[k][j] + dis[i][j]（i 到 j 的路径中，所有结点编号都小于 k 的最短路径长度）。根据 Floyd 的原理，在最外层循环做了 k-1 次之后，dist[i][j] 则代表了 i 到 j 的路径中，所有结点编号都小于 k 的最短路径。故该算法一定能找到图中最小环。代码如下：

void floyd() {
  for(int k = 1; k <= n; ++k) {  // 求最小环,不包含第k个点
    for(int i = 1; i < k; ++i) {    // 到k-1即可
      for(int j = i + 1; j < k; j++)  // 到k-1即可
        mincircle = min(mincircle , dis[i][j] + g[i][k] + g[k][j]);    //无向图 
    }

    for(int i = 1; i <= n; ++i)  // 更新最短路
      for(int j = 1; j <= n; ++j)
          dis[i][j] = min(dis[i][k] + dis[k][j] , dis[i][j]);
  }
}

Floyd 还有很多用途，限于篇幅不再赘述了。

 　　　　　　　　　　　　　　　　　　　　　　　　—— 还记得那天的景色，就像真的到达了那个世界。