Floyd 多源最短路, dp

void 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]); // f[i][j]表示i到j的最短路
}

CF400D Dima and Bacteria

1. 边权为0时, 并查集合并;

2. 枚举所有点的编号, 检查同一类型的点是否都在一个集合里;

3. 将一个联通块视为一个大点, 跑floyd;

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

const int N = 1e5, M = 510, INF = 0x3f3f3f3f;
int a[N], b[N], w[N];
int c[N], id[N];
int p[N];
int f[M][M];

int find(int x)
{
     if (p[x] != x) p[x] = find(p[x]);

     return p[x];
}

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

    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) p[i] = i;

    memset(f, 0x3f, sizeof f);

    for (int i = 1; i <= k; i++)
    {
        cin >> c[i];

        f[i][i] = 0;
    }

    for (int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i] >> w[i];

        int x = find(a[i]), y = find(b[i]);

        if (!w[i] && x != y) p[y] = x;
    }

    int cnt = 0;
    for (int i = 1; i <= k; i++)
    {
        for (int j = cnt + 1; j <= cnt + c[i]; j++)
        {
            id[j] = i;

            if (find(j) != find(cnt + 1))
            {
                cout << "No";
                return 0;
            }
        }

        cnt += c[i];
    }

    cout << "Yes\n";

    for (int i = 1; i <= m; i++)
    {
        int x = id[a[i]], y = id[b[i]];

        f[x][y] = f[y][x] = min(f[x][y], w[i]);
    }

    for (int l = 1; l <= k; l++)
        for (int i = 1; i <= k; i++)
            for (int j = 1; j <= k; j++)
                f[i][j] = min(f[i][j], f[i][l] + f[l][j]);

    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= k; j++)
            if (f[i][j] == INF) cout << "-1 ";
            else cout << f[i][j] << ' ';

        cout << '\n';
    }


    return 0;
}

P1119 灾后重建

就是把floyd分成了很多次 😊

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

const int N = 210, INF = 0x3f3f3f3f;
int t[N];
bool st[N];
int f[N][N];

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

    int n, m;
    cin >> n >> m;

    memset(f, 0x3f, sizeof f);

    for (int i = 0; i < n; i++) f[i][i] = 0;

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

    int a, b, c;
    while (m--)
    {
        cin >> a >> b >> c;

        f[a][b] = f[b][a] = c;
    }

    cin >> m;

    while (m--)
    {
        cin >> a >> b >> c;

        for (int k = 0; k < n; k++)
            if (t[k] <= c)
                if (!st[k])
                {
                    st[k] = true;

                    for (int i = 0; i < n; i++)
                        for (int j = 0; j < n; j++)
                            if (f[i][j] > f[i][k] + f[k][j])
                                f[i][j] = f[i][k] + f[k][j];
                }

        if (t[a] <= c && t[b] <= c && f[a][b] < INF) cout << f[a][b] << '\n';
        else cout << "-1\n";
    }


    return 0;
}

P1841 [JSOI2007] 重要的城市

重要的点也就是在floyd过程中通过k更优的点, 每次记录下来, 最后的时候判断一下就行了

!!! 注意floyd过程中,不能自环,不然会把原来的记录覆盖掉

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

const int N = 210;
bool st[N];
int f[N][N], g[N][N];

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

    int n, m;
    cin >> n >> m;

    memset(f, 0x3f, sizeof f);

    int a, b, c;
    while (m--)
    {
        cin >> a >> b >> c;

        f[a][b] = f[b][a] = min(f[a][b], c);
    }

    for (int i = 1; i <= n; i++) f[i][i] = 0;

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j && i != k && j != k)
                {
                    if (f[i][k] + f[k][j] < f[i][j]) // 松弛成功
                        f[i][j] = f[i][k] + f[k][j], g[i][j] = k; // 存i到j当前最后一个中转点k
                    else if (f[i][k] + f[k][j] == f[i][j])g[i][j] = -1; // 最后一次中转点不唯一
                }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (~g[i][j]) st[g[i][j]] = true;

    bool flag = true;
    for (int i = 1; i <= n; i++)
        if (st[i])
        {
            cout << i << ' ';
            flag = false;
        }

    if (flag) cout << "No important cities.";


    return 0;
}