游览计划 题解

题意

给定一张无向图，选取四个点 \(a \ne b \ne c \ne d\)，求 \(f(a, b) + f(b, c) + f(c, d)\) 的最大值，其中 \(f(u, v)\) 表示点 \(u\) 到点 \(v\) 的最短路长度。

题解

如果顺着枚举四个点 \(a\)、\(b\)、\(c\)、\(d\)，是一个 \(n^4\) 的复杂度，显然过不了。

但是我们发现如果确定了 \(a\)、\(b\)、\(c\)，那么 \(d\) 可以贪心找到离 \(c\) 最远的且不为 \(a\)、\(b\) 的点。

复杂度降到了 \(n^3\)，但还是过不了（赛时就分析到了这里就没往下想了）。

但 \(b\) 点也同理，\(b\) 点确定了，找最远的 \(a\) 即可。

我们维护一个 \(g(u)\)，表示离 \(u\) 点最远的点即可。

但是不对，题目要求 \(a \ne b \ne c \ne d\)，倘若 \(g(b) = c\)，就无法满足条件，就成功地挂了。

所以我们需要维护一个 \(g(u, 0 \sim 2)\)，表示离 \(u\) 最远、次远、次次远的点。

此时就很好解决了。

说说前面的最短路。

如果直接跑弗洛伊德会爆掉，但是由于边权为 \(1\)，所以可以跑 \(n\) 次 bfs，时间复杂度从 \(n^3\) 降到了 \(nm\)（赛时这个我也没想到）。

时间复杂度：\(\mathcal O(nm + n^2)\)。

namespace zqh {
const int N = 4005;

int n, m, dis[N][N];
int far[N][3];
vector<int> g[N];

il void bfs(int s) { // 求以 s 为起点的最短路
    queue<int> q;
    q.push(s);
    dis[s][s] = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (!dis[s][v]) {
                dis[s][v] = dis[s][u] + 1;
                q.push(v);
            }
        }
    }
}

il void init() {
    cin >> n >> m;
    for (rg int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

il void solve() {
    for (rg int i = 1; i <= n; i++) {
        bfs(i);
        dis[i][0] = -1;
    }
    for (rg int i = 1; i <= n; i++) { // far 就是上文的 g
        for (rg int j = 1; j <= n; j++) {
            // cout << dis[i][j] << " ";
            if (dis[i][j] == 0x3f3f3f3f3f3f3f3f || i == j)
                continue;
            if (dis[i][far[i][2]] < dis[i][j]) { // 一个判前三大的好方法
                far[i][2] = j;
            }
            if (dis[i][far[i][1]] < dis[i][far[i][2]]) {
                swap(far[i][1], far[i][2]);
            }
            if (dis[i][far[i][0]] < dis[i][far[i][1]]) {
                swap(far[i][0], far[i][1]);
            }
        }
        // cout << endl;
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << far[i][0] << " " << far[i][1] << " " << far[i][2] << endl;
    // }
    int ans = 0;
    for (rg int b = 1; b <= n; b++) { 
        for (rg int c = b + 1; c <= n; c++) { // 枚举 b、c
            for (rg int i = 0; i < 3; i++) {
                for (rg int j = 0; j < 3; j++) { // 枚举第几大
                    int a = far[b][i], d = far[c][j];
                    if (a != b && a != c && a != d && b != c && b != d &&
                        c != d) { // 不能重复
                        if (dis[a][b] + dis[b][c] + dis[c][d] > ans) {
                            ans = max(ans, dis[a][b] + dis[b][c] + dis[c][d]); // 统计答案
                            // cout << a << " " << b << " " << c << " " << d
                            //      << endl;
                        }
                    }
                }
            }
        }
    }
    cout << ans;
}

void main() {
    init();
    solve();
}
}  // namespace zqh