定义 d(k)ij 为只考虑 i 到 j 的路径中只包含前 k 个点的时候,从 i 到 j 的最短路径。
动态规划的思想,我们考虑 d(k)ij 和 d(k−1)ij 的关系,当加入点 k 的时候,也许通过点 k,可以更新从 i 到 j 的最短路径。
即 d(k)ij=min(d(k)ij,d(k−1)ik+d(k−1)kj)
初始条件d0ij={0,i==j w(i,j),i到j有边 INF,i到j没有边
代码实现:
// 如果你决定用floyd的话,那么存图就可以用邻接矩阵(因为已经没有省时间的必要了qwq)
// 邻接矩阵:用来存两点之间的边
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) d[i][j] = 0; // d数组表示两点之间的最短路径
else if (w[i][j]) d[i][j] = w[i][j]; // w数组表示两点之间的权值
else d[i][j] = INF;
}
}
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
注意 INF 的选择,不要太大,避免 INF+INF 溢出
如果在一个图论题中,如果点的个数不超过 500,那么可以考虑用 floyd
通常情况下是用 floyd 做一个预处理,然后套别的算法来解决问题
Floyd计算传递闭包
在有向图中,d[i][j] 如果是 1,表示 i 能到达 j。否则是 0 表示无法到达。根据初始到达关系,计算最终一个点能到达的其他点。
代码实现:
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
}
}
}
666
AT5215 这题也还可以,只不过luogu不支持提交了,可以去atcoder提交,建议加一下
好的,多谢大佬Orz