2022 CCF CSP-S2.假期计划

题目

4732. 假期计划

算法标签: 搜索, 枚举, 贪心

思路

最多转车$k$次等价于路线长度小于等于$k+1$, 经过的点没有限制, 注意到点的数量$2500$, 因此$n^2$的时间复杂度是可以考虑的, 边的数量$10000$, $n\times m$时间复杂度也可以接受, 相当于从每个点预处理一遍, 可以预处理出每个点到其他所有点的最短距离, 也可以预处理出每个点在$k+1$长度之内能到达的点
只能枚举两个点, 可以考虑枚举$b,c$两个点, 可以将所有方案分为$A_{n-1}^2$类

$a,d$两个点距离$1$的距离都不能超过$k+1$其实是属于一种限制, 因此$f[x]$表示所有与$1$不超过$k+1$的点集以及所有与$x$不超过$k+1$的不是$x$的点集, 因为预处理是从小到大, 因此$vis[1][x]$会首先处理, 后续判断直接查表

枚举$b,c$之后确定的关系是黑色线段, 但是要求每个景点是不同的, 因此对于点$a$还需要判断是否和$c$或者$d$相同, 对于点$b$仍需要判断是否和$d$相同

直接枚举的时间复杂是$O(n^4)$是无法接受的, 因此需要进行优化, 注意到对于点$a$来说, 只需要和$c,d$两个点不同就可以, 因此只需要找出$a$能到达的最大的三个值参与贡献, 对于点$d$也是同样的道理, 这样就能将$n^2$优化到$9$

优化后时间复杂度$O(n^2+9\times n^2)$

插入排序写法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef long long LL;
const int N = 2510, M = 20010;int n, m, k;
LL w[N];
vector<int> head[N];
int d[N], f[N][4];
bool vis[N][N];void add(int u, int v) {head[u].push_back(v);
}void bfs(int s, int f[]) {int q[N];int h = 0, t = -1;memset(d, 0x3f, sizeof d);d[s] = 0;q[++t] = s;while (h <= t) {int u = q[h++];if (d[u] == k + 1) continue;for (int v : head[u]) {if (d[u] + 1 < d[v]) {d[v] = d[u] + 1;vis[s][v] = true;q[++t] = v;if (vis[1][v]) {f[3] = v;for (int i = 3; i; --i) {if (w[f[i]] > w[f[i - 1]]) swap(f[i], f[i - 1]);else break;}}}}}
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m >> k;for (int i = 2; i <= n; ++i) cin >> w[i];for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;add(u, v);add(v, u);}for (int i = 1; i <= n; ++i) bfs(i, f[i]);LL ans = 0;// 枚举b, c两个点for (int b = 2; b <= n; ++b) {for (int c = 2; c <= n; ++c) {if (vis[b][c]) {for (int x = 0; x < 3; ++x) {for (int y = 0; y < 3; ++y) {int a = f[b][x], d = f[c][y];if (a && d && a != d && a != c && b != d) {ans = max(ans, w[a] + w[b] + w[c] + w[d]);}}}}}}cout << ans << "\n";return 0;
}

$sort$写法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef long long LL;
const int N = 2510, M = 20010;int n, m, k;
LL w[N];
vector<int> head[N];
int d[N], f[N][4];
bool vis[N][N];void add(int u, int v) {head[u].push_back(v);
}bool cmp(const int a, const int b) {return w[a] > w[b];
}void bfs(int s, int f[]) {int q[N];int h = 0, t = -1;memset(d, 0x3f, sizeof d);d[s] = 0;q[++t] = s;while (h <= t) {int u = q[h++];if (d[u] == k + 1) continue;for (int v : head[u]) {if (d[u] + 1 < d[v]) {d[v] = d[u] + 1;vis[s][v] = true;q[++t] = v;if (vis[1][v]) {f[3] = v;sort(f, f + 4, cmp);}}}}
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m >> k;for (int i = 2; i <= n; ++i) cin >> w[i];for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;add(u, v);add(v, u);}for (int i = 1; i <= n; ++i) bfs(i, f[i]);LL ans = 0;// 枚举b, c两个点for (int b = 2; b <= n; ++b) {for (int c = 2; c <= n; ++c) {if (vis[b][c]) {for (int x = 0; x < 3; ++x) {for (int y = 0; y < 3; ++y) {int a = f[b][x], d = f[c][y];if (a && d && a != d && a != c && b != d) {ans = max(ans, w[a] + w[b] + w[c] + w[d]);}}}}}}cout << ans << "\n";return 0;
}