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;
}