P2910 [USACO08OPEN] Clear And Present Danger S 题解

littlesnake · 2024-02-06 17:49:40 · 题解

前言

刚学习了 Floyd 算法，就想来写个题解，如果题解没有通过的话，就当作个人笔记好了。

我看题解区第一篇题解就只是简单讲了一下，又贴了个代码。我将在此题解中使用 2 种算法求解，比较它们的时间复杂度、空间复杂度，以及它们的耗时。并且讲解 Floyd 算法的原理。

分析

这道题是一个最短路题，但是它与其它题目不同之处在于它需要处理从不同点出发的最短路径，也就是多源最短路径。点的数量较少，但是任意两点之间都有连边（边的数量约为 O(n^2) 级别）。最简单的方法是采用 n 遍 Dijkstra 算法求最短路，其时间复杂度为 O(n^3)，已经足够通过本题。

代码如下：

#include <bits/stdc++.h>
#define MAXN 105
#define MAXM 10005
#define inf 2147483647
using namespace std;
// 有点混乱，d 数组是 Dijkstra 用的
int n, m, ans, a[MAXM], dis[MAXN][MAXN], d[MAXN];
bool vis[MAXN];
// 裸的 Dijkstra
int Dijkstra(int b, int e) {
    memset(vis, 0, sizeof(vis)); // 需要初始化
    for(int i = 1; i <= n; i++) d[i] = inf;
    d[b] = 0;
    while(!vis[e]) {
        vis[b] = 1;
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;
            if(d[b] + dis[b][i] < d[i]) 
                d[i] = d[b] + dis[b][i];
        }
        int minn = inf;
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;
            if(d[i] < minn) {
                minn = d[i];
                b = i;
            }
        }
    }
    return d[e];
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> dis[i][j];
    for(int i = 1; i < m; i++)
        ans += Dijkstra(a[i], a[i + 1]);
    cout << ans;
    return 0;
}

耗时 517ms。

但事实上，对于多源最短路，可以使用 Floyd-Warshall 算法（简称 Floyd 算法）更便捷地解决此类问题。

采用动态规划的思路，设 dis_{i,j,k} 表示当只途径编号为 1 到 k 的点时（起始点和终点不算），i 到 j 的最短路的长度。特别地，dis_{i,j,0} 代表初始时 i、j 点间的边的边权。

考虑如何进行状态更新，显然从 i 到 j 且只经过编号为 1 到 k 的点的路径分为两类：

1. 从 i 到 j，且只经过编号为 1 到 k - 1 的路径；

2. 从 i 到 k，再从 k 到 j，且只经过编号为 1 到 k 的点的路径。

显然对于第一类路径，最短者的长度就是 dis_{i,j,k - 1}。对于第二类路径，最短者的长度就是 dis_{i,k,k - 1} + dis_{k,j,k - 1}。两者当中取最小值，就得到转移方程：

然后只需要依次枚举 k,i,j，并进行转移即可。最终结果为第三维为 n 的数组。注意由于再第三维为 k 的时候需要用到第三维为 k - 1 的数据，所以在枚举是应当先枚举第三维 k，再枚举 i 和 j。

代码非常简短，如下所示：

for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            dis[i][j][k] = min(dis[i][j][k - 1], dis[i][k][k - 1] + dis[k][j][k - 1]);

时间复杂度 O(n^3)，空间复杂度 O(n^3)。在时间上已经难以对该算法进行优化，但在空间上可以。

显然 dis_{i,k,k - 1} 与 dis_{i,k,k}、dis_{k,j,k - 1} 与 dis_{k,j,k} 分别都相等，所以我们可以发现数组第三维 k 是多余的，可以直接使用二维数组来解决本题。这种优化方式叫做滚动优化，在动态规划算法里经常使用。转移方程则变为：

空间复杂度变为 O(n^2)，时间复杂度不变。最终代码如下：

#include <bits/stdc++.h>
#define MAXN 105
#define MAXM 10005
using namespace std;
int n, m, a[MAXM], dis[MAXN][MAXN];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> dis[i][j];
    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((long long)dis[i][j], (long long)dis[i][k] + dis[k][j]);
    int ans = 0;
    for(int i = 1; i <= m - 1; i++)
        ans += dis[a[i]][a[i + 1]];
    cout << ans;
    return 0;
}

耗时 41ms。

可以证明，当存在负权边时 Floyd 算法正确性可以保证。Floyd 算法既可以处理无向图，也可以处理有向图，注意设置 dis 的初始值即可。

但是为什么 Floyd 算法和 Dijkstra 算法运行的时间相差这么多呢？

因为 Dijkstra 是单源最短路径算法，而 Floyd 是多源最短路径算法。

小结

每种算法都有自己擅长的方面，没有最好的算法，只有适合的题目。