Floyd算法进阶：从图论连通性问题到矩阵快速幂优化
在近期的一场图论专项模拟赛中，主要围绕Floyd算法及其变体展开，以下是对三道经典题目的深入分析和解题思路复盘。
A. 牧场的旅行：连通块与直径计算
本题源自洛谷 P1522，核心问题是如何连接两个不同牧场的点以最小化新牧场的直径。
关键思路分为三步：首先使用并查集预处理连通块；然后运行Floyd算法计算所有点对之间的最短距离；最后枚举所有可能连接的点对。
定义 mx[i] 为从点i出发到达其连通块内最远点的距离，t[block] 为整个连通块的直径（即块内所有 mx 的最大值）。当连接点i和点j（分属不同连通块）时，新直径取三者最大值：两个原始连通块直径、以及 mx[i] + dis(i,j) + mx[j]。
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 202;
const db INF = 0x3fffffff;
char grid[N][N];
int n, parent[N];
db xs[N], ys[N];
db dist[N][N], maxDist[N], blockDia[N];
db calcDist(int i, int j) {
return sqrt((xs[i]-xs[j])*(xs[i]-xs[j]) + (ys[i]-ys[j])*(ys[i]-ys[j]));
}
int findRoot(int x) {
return parent[x] == x ? x : parent[x] = findRoot(parent[x]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
parent[i] = i;
scanf("%lf%lf", &xs[i], &ys[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%s", grid[i] + 1);
for (int j = 1; j <= n; j++) {
if (grid[i][j] == '1') {
dist[i][j] = calcDist(i, j);
parent[findRoot(i)] = findRoot(j);
} else if (i != j) dist[i][j] = INF;
}
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (findRoot(i) == findRoot(j)) maxDist[i] = max(maxDist[i], dist[i][j]);
blockDia[findRoot(i)] = max(blockDia[findRoot(i)], maxDist[i]);
}
db result = INF;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (findRoot(i) != findRoot(j)) {
db newDia = max(maxDist[i] + calcDist(i, j) + maxDist[j],
max(blockDia[findRoot(i)], blockDia[findRoot(j)]));
result = min(result, newDia);
}
printf("%.6lf", result);
return 0;
}
B. 快速米变速：2^k 距离与倍增思想
该题来自洛谷 P1613，关键点在于"2^k"的行驶距离，自然联想到倍增法。
定义状态 can[i][j][k] 表示是否存在一条从i到j长度为2^k的路径。若 can[i][mid][k-1] 和 can[mid][j][k-1] 都成立，则 can[i][j][k] 为真，且此时 dis[i][j] 可设为1。最后通过Floyd求出最短路径数。
#include <bits/stdc++.h>
using namespace std;
const int N = 55, K = 70;
int n, m, u, v;
bool reach[N][N][K];
int graph[N][N];
int main() {
scanf("%d%d", &n, &m);
memset(graph, 0x3f, sizeof graph);
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
reach[u][v][0] = true;
graph[u][v] = 1;
}
for (int k = 0; k < 64; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int mid = 1; mid <= n; mid++)
if (reach[i][mid][k] && reach[mid][j][k]) {
reach[i][j][k+1] = true;
graph[i][j] = 1;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
printf("%d", graph[1][n]);
return 0;
}
C. 最短路径变体：精确边数约束与矩阵快速幂
本题源自洛谷 P2886，要求恰好经过n条边（n可达10^6）的最短路。由于边数仅100，但顶点编号可达1000，需先离散化。
关键优化：将Floyd看作矩阵乘法。定义矩阵A表示经过x条边的最短路径，矩阵B表示经过y条边的最短路径，则合并后矩阵C表示经过x+y条边的最短路径，公式为 C[i][j] = min(A[i][k] + B[k][j])。通过快速幂思想，只需log(n)次矩阵乘法。
注意：需要转移n-1次而非n次；某些OJ需要输出-1表示无解。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, edgeCnt, src, dst, total;
int mapping[1010];
struct Matrix {
int data[120][120];
Matrix operator*(const Matrix &other) const {
Matrix res;
memset(res.data, INF, sizeof res.data);
for (int k = 1; k <= total; k++)
for (int i = 1; i <= total; i++)
for (int j = 1; j <= total; j++)
res.data[i][j] = min(res.data[i][j],
data[i][k] + other.data[k][j]);
return res;
}
} base, answer;
int main() {
memset(base.data, INF, sizeof base.data);
scanf("%d%d%d%d", &n, &edgeCnt, &src, &dst);
while (edgeCnt--) {
int w, a, b;
scanf("%d%d%d", &w, &a, &b);
if (!mapping[a]) mapping[a] = ++total;
if (!mapping[b]) mapping[b] = ++total;
int u = mapping[a], v = mapping[b];
base.data[u][v] = base.data[v][u] = w;
}
n--;
answer = base;
while (n) {
if (n & 1) answer = answer * base;
base = base * base;
n >>= 1;
}
printf("%d", answer.data[mapping[src]][mapping[dst]]);
return 0;
}
以上三道题展示了Floyd算法在不同场景下的灵活运用：从基础连通块计算，到倍增思想处理2^k约束，再到矩阵快速幂优化大量边数限制。掌握这些变体对深入理解图论算法很有帮助。
