NO.96十六届蓝桥杯备战|图论基础-多源最短路|Floyd|Clear And Present Danger|灾后重建|无向图的最小环问题(C++)

多源最短路：即图中每对顶点间的最短路径

floyd算法本质是动态规划，⽤来求任意两个结点之间的最短路，也称插点法。通过不断在两点之间加⼊新的点，来更新最短路。
适⽤于任何图，不管有向⽆向，边权正负，但是最短路必须存在（也就是不存在负环）。

1. 状态表⽰： f[k][i][j] 表⽰：仅仅经过 [1, k] 这些点，结点 i ⾛到结点 j 的最短路径的⻓度。
2. 状态转移⽅程：

• 第⼀种情况，不选新来的点： f[k][i][j] = f[k - 1][i][j] ；
• 第⼆种情况，选择新来的点： f[k][i][j] = f[k - 1][i][k] + f[k - 1][k][j]

3. 空间优化：只会⽤到上⼀层的状态，因此可以优化到第⼀维。
4. 初始化：

• f[i][i] = 0 ；
• f[i][j] 为初始状态下 i 到 j 的距离，如果没有边则为⽆穷。

5. 填表顺序：

• ⼀定要先枚举 k ，再枚举 i 和 j 。因为我们填表的时候，需要依赖的是 k - 1 层的状态，因此 k 必须先枚举。

B3647 【模板】Floyd - 洛谷

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int n, m;
int f[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    memset(f, 0x3f, sizeof f);

    for (int i = 1; i <= n; i++) f[i][i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        f[a][b] = f[b][a] = min(f[a][b], c);
    }

    //floyd
    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], f[i][k] + f[k][j]);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << f[i][j] << " ";
        cout << endl;
    }
    
    return 0;
}

P2910 [USACO08OPEN] Clear And Present Danger S - 洛谷

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 110, M = 1e4 + 10;

int n, m;
int a[M];
int f[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    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 >> f[i][j];

    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], f[i][k] + f[k][j]);

    LL ret = 0;
    for (int i = 2; i <= m; i++)
    {
        int x = a[i-1], y = a[i];
        ret += f[x][y];
    }
    cout << ret << endl;
    
    return 0;
}

P1119 灾后重建 - 洛谷

在floyd算法中，我们是⼀个点⼀个点加⼊到最短路的更新中，那么这道题其实就是限制了我们加点的时机。当从前往后遍历每次询问的时候，直到时间点在询问的时间t之前的点，都可以加⼊到最短路的更新中。
那么就可以⼀边读取询问，⼀边通过时间限制，更新最短路

#include <bits/stdc++.h>
using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n, m;
int t[N];
int f[N][N];

void floyd(int 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]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < n; i++) f[i][i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        f[a][b] = f[b][a] = min(f[a][b], c);
    }

    int Q; cin >> Q;
    int pos = 0;
    while (Q--)
    {
        int a, b, c; cin >> a >> b >> c;
        while (pos < n && t[pos] <= c) floyd(pos++);

        if (t[a] > c || t[b] > c || f[a][b] == INF) cout << -1 << endl;
        else cout << f[a][b] << endl;
    }
    
    return 0;
}

P6175 无向图的最小环问题 - 洛谷

floyd算法的性质：

• 在计算第 k 层的时候， f[i][j] ⾥⾯存储着中转点为 [1, k - 1] 时的最短路。如果设环⾥的最⼤结点的编号为 k ，与k相邻的点为 i, j ，其中 i < k && j < k && i != j ：
• 那么我们在floyd算法循环到 k 的时候，这个环的最⼩⻓度为： f[i][j] + e[i][k] + e[j][k] 。
• 环的最⼤编号是任意的，因此在所有情况下取最⼩值即可

#include <bits/stdc++.h>
using namespace std;

const int N = 110, INF = 1e8;

int n, m;
int e[N][N];
int f[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    //memset(e, 0x3f, sizeof e);
    //memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = e[i][j] = INF;
    
    for (int i = 1; i <= n; i++) e[i][i] = f[i][i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        e[a][b] = e[b][a] = f[a][b] = f[b][a] = min(e[a][b], c);
    }

    int ret = INF;
    for (int k = 1; k <= n; k++)
    {
         //最小环
        for (int i = 1; i < k; i++)
            for (int j = i+1; j < k; j++)
                ret = min(ret, f[i][j] + e[i][k] + e[k][j]);

        //最短距离
        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 (ret == INF) cout << "No solution." << endl;
    else cout << ret << endl;

    return 0;
}