「CSP-S 2022」假期计划 - 最短路 + BFS + 贪心

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

小熊的地图上有 \(n\) 个点，其中编号为 \(1\) 的是它的家、编号为 \(2, 3, \ldots, n\) 的都是景点。部分点对之间有双向直达的公交线路。如果点 \(x\) 与 \(z_1\)、\(z_1\) 与 \(z_2\)、……、\(z_{k - 1}\) 与 \(z_k\)、\(z_k\) 与 \(y\) 之间均有直达的线路，那么我们称 \(x\) 与 \(y\) 之间的行程可转车 \(k\) 次通达；特别地，如果点 \(x\) 与 \(y\) 之间有直达的线路，则称可转车 \(0\) 次通达。

很快就要放假了，小熊计划从家出发去 \(4\) 个不同的景点游玩，完成 \(5\) 段行程后回家：家 \(\to\) 景点 A \(\to\) 景点 B \(\to\) 景点 C \(\to\) 景点 D \(\to\) 家且每段行程最多转车 \(k\) 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A \(\to\) 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D \(\to\) 家这段行程转车时经过的点。

假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

对于所有数据，保证 \(5 \le n \le 2500\)，\(1 \le m \le 10000\)，\(0 \le k \le 100\)，所有景点的分数 \(1 \le s_i \le {10}^{18}\)。保证至少存在一组符合要求的行程。

解题思路

首先我们可以先在预处理，每个点跑一遍 BFS 求出从 \(u\) 到 \(v\) 的最小步数 \(\text{step}_{u, v}\)。

对于一种部分分写法，我们可以把 \(\text{step}_{u, v} \le k + 1\) 的边连起来，然后跑一遍深度为 \(4\) 的 DFS。但这样如果数据构造出菊花图或点数多后很容易爆炸，实际得分 70pts。

接下来我们可以想优化，由于只需经过 \(4\) 个点，我们可以考虑枚举经过的点。根据数据范围和题目信息，很容易推出我们需要枚举 \(2\) 个点，然后计算出最优的另外两个点即可。为了让可选点的限制尽量多，我们可选择枚举 \(B\) 和 \(C\) 两点。这样我们只需要算出 \(B/C \rightarrow 1\) 所经过的唯一最优点即可。

在枚举的时候寻找可行的点显然不可行，于是我们可以想到对每个点 \(u\)，预处理满足 \(\text{step}_{1, v} \le k + 1 \wedge \text{step}_{v, i} \le k + 1\) 的所有 \(v\) 点。将所有 \(v\) 点存入 \(\text{att}_u\) 数组，然后根据每个点的分数从大到小将 \(\text{att}_u\) 排序。时间复杂度 \(O(n^2)\)。

最后我们枚举 \(B\)、\(C\) 两点，然后分别从 \(\text{att}_B\) 和 \(\text{att}_C\) 中选择不重复的 \(A\)、\(D\) 点即可。使用贪心可以证明最优的 \(A\)、\(D\) 点始终为 \(\text{att}_B\) 和 \(\text{att}_D\) 的前 \(3\) 项，于是对于每组 \(B\)、\(D\) 仅需枚举 \(9\) 次。得出所有情况的最大值即为答案。时间复杂度为 \(O(n^2)\)。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <climits>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

struct Node {
    int id;
    std::vector<struct Edge> e;
    unsigned long long s;
    bool v;
};

struct Edge {
    Node *s, *t;

    Edge(Node *s, Node *t) : s(s), t(t) {}
};

inline void addEdge(Node *s, Node *t) {
    s->e.push_back(Edge(s, t));
    t->e.push_back(Edge(t, s));
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    k++;

    std::vector<Node> nodes(n + 1);
    for (int i = 1; i <= n; i++) nodes[i].id = i;
    for (int i = 2; i <= n; i++) scanf("%lld", &nodes[i].s);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        addEdge(&nodes[x], &nodes[y]);
    }

    std::vector<std::vector<int>> steps(n + 1, std::vector<int>(n + 1, INT_MAX));

    auto bfs = [&](Node *u) {
        for (int i = 1; i <= n; i++) nodes[i].v = false;

        std::queue<std::pair<int, Node *>> q;
        u->v = true, steps[u->id][u->id] = 0;
        q.push(std::make_pair(0, u));

        while (!q.empty()) {
            const std::pair<int, Node *> p = q.front();
            q.pop();
            int step = p.first;
            Node *v = p.second;

            for (Edge &e : v->e) {
                if (!e.t->v) {
                    steps[u->id][e.t->id] = step + 1;
                    e.t->v = true;
                    q.push(std::make_pair(step + 1, e.t));
                }
            }
        }
    };

    for (int i = 1; i <= n; i++) bfs(&nodes[i]);

    std::vector<std::vector<Node *>> att(n + 1);
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            if (i == j) continue;
            if (steps[i][j] <= k && steps[j][1] <= k) {
                att[i].push_back(&nodes[j]);
            }
        }
    }
    for (int i = 2; i <= n; i++) std::sort(att[i].begin(), att[i].end(), [](Node *a, Node *b){ return a->s > b->s; });

    unsigned long long ans = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            if (i == j || steps[i][j] > k || att[i].empty() || att[j].empty()) continue;
            std::vector<Node *>::iterator itB = att[i].begin(), itC = att[j].begin();
            if (*itB == &nodes[j]) itB++;
            if (*itC == &nodes[i]) itC++;
            if (itB == att[i].end() || itC == att[j].end()) continue;
            if (*itB == *itC) {
                if (itB + 1 != att[i].end() && *(itB + 1) != &nodes[j] && *(itB + 1) != *itC) ans = std::max(ans, nodes[i].s + nodes[j].s + (*(itB + 1))->s + (*itC)->s);
                if (itC + 1 != att[j].end() && *(itC + 1) != &nodes[i] && *(itC + 1) != *itB) ans = std::max(ans, nodes[i].s + nodes[j].s + (*itB)->s + (*(itC + 1))->s);
            } else ans = std::max(ans, nodes[i].s + nodes[j].s + (*itB)->s + (*itC)->s);
        }
    }

    printf("%lld\n", ans);

    return 0;
}