更进一步的感悟 floyd 内涵！
了解 & 理解 floyd：
floyd 算法，常用于求多源最短路，O(n^3)。
本质是动态规划。两个点，通过找中转点更新答案。
三个 for。其中第一个 for 枚举 k 表示除了起点终点外只允许前走 1~k 个点的答案。另外两个 for 枚举起点终点。
例题 1：P1119 灾后重建：加强对枚举 k 过程的理解。
注意到 t_0 <= t_1 <= ... <= t_N-1，且询问序列不下降，这恰好符合了 floyd 的要求。
于是我们把枚举 k 跑 floyd 的过程移到每次询问中处理，由于询问序列不下降，所以每次枚举的 k 只要保证了 t[k] <= z 即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 202;
int n, m, q;
int a[N], f[N][N];
int main()
{
scanf("%d%d", &n, &m);
memset(f, 0x3f, sizeof f);
for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
while(m -- )
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
f[x][y] = min(f[x][y], z);
f[y][x] = min(f[y][x], z);
}
scanf("%d", &q);
int k = -1;
while(q -- )
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
while(k + 1 < n && a[k + 1] <= z)
{
k ++;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < n; j ++ )
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
if(f[x][y] == 0x3f3f3f3f || a[x] > z || a[y] > z) puts("-1");
else printf("%d\n", f[x][y]);
}
return 0;
}
例题 2：P2966 [USACO09DEC] Cow Toll Paths G：最短路径涉及到最大点权。
首先考虑到枚举中转点 k 的顺序不会影响答案，所以想一下怎么按照点权先来进行一个排序。
可以将点权从小到大排序，这样考虑最大点权时，a[k].v 即能代表在 i 到 j 的路径上除了 i 和 j 的最大点权，最大点权就是比较 i、j、k。这样排序的时候单独标一下编号即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 253;
const int inf = 0x3f;
int n, m, q;
int d[N][N], f[N][N];
struct node{int v, num;}a[N];
bool cmp(node x, node y){return x.v < y.v;}
int main()
{
scanf("%d%d%d", &n, &m, &q);
memset(f, inf, sizeof f);
memset(d, inf, sizeof d);
for(int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i].v);
a[i].num = i;
d[i][i] = 0;
}
sort(a + 1, a + n + 1, cmp);
while(m -- )
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
d[x][y] = min(d[x][y], z);
d[y][x] = min(d[y][x], z);
}
for(int k = 1; k <= n; k ++ )
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
int x = a[i].num, y = a[j].num, z = a[k].num;
d[x][y] = min(d[x][y], d[x][z] + d[z][y]);
f[x][y] = min(f[x][y], d[x][y] + max(a[i].v, max(a[j].v, a[k].v)));
}
while(q -- )
{
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", f[x][y]);
}
return 0;
}
例题 3：P2888 [USACO07NOV] Cow Hurdles S：路径上的最大值最小。
（两年前做过这道题，震惊的，一点没进步是吧。）
就是把跑最短路的过程换成了跑两点之间最小的最大值。很板子了。
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, t;
int f[310][310];
int main()
{
memset(f, inf, sizeof f);
scanf("%d%d%d", &n, &m, &t);
while(m -- )
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
f[x][y] = min(z, f[x][y]);
}
for(int k = 1; k <= n; k ++ )
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ ) f[i][j] = min(f[i][j], max(f[i][k], f[k][j]));
while(t -- )
{
int x, y;
scanf("%d%d", &x, &y);
if(f[x][y] == inf) puts("-1");
else printf("%d\n", f[x][y]);
}
return 0;
}
例题 4：P2419 [USACO08JAN] Cow Contest S：求传递闭包。
看到题的第一反应是拓扑排序，好像不是很好写；第二反应是 dfs，好像也不是很好写；如你所见，第三反应是套 floyd。
考虑当一个数知道它与其他 n - 1 个数的大小关系后就可以确定排名了。直接跑就完事了。
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int ans;
int f[N][N];
int main()
{
scanf("%d%d", &n, &m);
while(m -- )
{
int x, y;
scanf("%d%d", &x, &y);
f[x][y] = 1;
}
for(int k = 1; k <= n; k ++ )
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ ) f[i][j] |= f[i][k] && f[k][j];
for(int i = 1; i <= n; i ++ )
{
int flag = 1;
for(int j = 1; j <= n; j ++ )
{
if(i != j && f[i][j] == 0 && f[j][i] == 0)
{
flag = 0;
break;
}
}
ans += flag;
}
printf("%d", ans);
return 0;
}
例题 5：hdu 1599.find the mincost route：求最小环。
无向图，那 i 点到 j 点之间的最小环可以表示为 i 到 j 之间的最小距离加上 j 到中转点 k、k 到 i 的直接距离。
k 直接枚举就好。
为了防止这两条路重合，只要保证当前 i 到 j 之间求最小距离的中转点只能为 1 ~ k-1。因为从 i 到 j 和 j 到 i 无区别，所以枚举 j 时可以直接从 i + 1 开始节省一定时间。
这样我们每一次枚举 k 时，先跑一遍最小环，再跑 floyd。
特别注意 ll 数组最好别用 memset。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 302;
const ll inf = 0x7fffffffff;
int n, m;
ll f[N][N], a[N][N];
void solve()
{
for(int i = 1; i < N; i ++ ) for(int j = 1; j < N; j ++ ) f[i][j] = a[i][j] = inf;
while(m -- )
{
int x, y;
ll z;
scanf("%d%d%lld", &x, &y, &z);
a[x][y] = a[y][x] = f[x][y] = f[y][x] = min(a[x][y], z);
}
ll minn = inf;
for(int k = 1; k <= n; k ++ )
{
for(int i = 1; i < k; i ++ )
for(int j = i + 1; j < k; j ++ ) minn = min(minn, f[i][j] + a[j][k] + a[k][i]);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ ) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
if(minn != inf) printf("%lld\n", minn);
else puts("-1");
}
int main()
{
while(~scanf("%d%d", &n, &m)) solve();
return 0;
}
一定程度上加深了我对 floyd 尤其是这个 k 的认识。以后我再做了什么相关好题还会继续补充 qwq。