Floyd 原理简析
Floyd 的原理其实是 DP,定义 \(\mathrm{dp}[S][i][j]\) 表示在仅经过点集 \(S\) 里的点的条件下,从 \(i\) 到 \(j\) 的最短路距离
初始状态 \(S\) 为空,\(\mathrm{dp}[\varnothing ][i][j]\) 就等于 \(i,j\) 间的边长,没有边就是正无穷
转移方程,在加入一个新的点 \(k\) 的时候,
\[\mathrm{dp}[S+k][i][j] = \max\{ \mathrm{dp}[S][i][j], \mathrm{dp}[S][i][k] + \mathrm{dp}[S][k][j]\} \]也就是说,每一次状态转移都是选取一个新点 \(k\),然后枚举所有的路径进行更新:将路径 \(<i, j>\) 拆成了 \(<i, k>,<k,j>\) 两段,比较这个有新点的路径是不是更优的,择优更新
因为每次更新之前 \(\mathrm{dp}[S][...][...]\) 都是已知的(要么是无法到达的 inf,要么是当前最优的答案),所以往后推每一次都是最优的
对于某一条最短路径 \(<i, j, k, l>\) ,虽然它在初始状态是无法联通的,但是随着新点的加入,\(<i, j, k>, <j, k, l>\) 终将联通,最后无论选择 \(j\) 还是 \(k\) 都能让 \(<i, j, k, l>\) 联通,只需选择最短的一条就可以得出答案了
写成代码的话一般都是按标号顺序更新点集,也就是 \(\mathrm{dp}[k][i][j]\) 表示考虑前 \(k\) 个点时的最短路径
然后再滚动掉第一维,就成了我们最后看到的样子:
int dist[MAXN][MAXN];
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
CF 295 B Greg and Graph
看完上面的原理,为什么要倒序跑 Floyd 就很显然了,Floyd 的原理本来就是加点,放在这题自然再合适不过
标签:Graph,路径,CF,295B,Floyd,dp,mathrm From: https://www.cnblogs.com/handwer/p/17588758.html