CSP-S 2022 T1假期计划

CSP-S 2022 T1假期计划

先思考暴力做法，题目需要找到四个不相同的景点，那我们就枚举这四个景点，判断它们之间的距离是否符合条件，条件是任意两个点之间的距离是否大于$k$，所以我们需要求出任意两点之间的距离。常用的$Dijkstra$和$SPFA$都是单源最短路，也就是只能求一个点到其它点的距离，而$Floyed$可以求任意两个点之间的最短路，虽然其时间复杂度是$O(n^3)$，但对于这个做法的数据范围是可以接受的。这个做法的时间复杂度为$O(n^4)$（枚举四个景点），在$k$较小的情况下可以通过（因为$k$会影响到循环退出），可以拿到$55$分。

#include <bits/stdc++.h>
#define A 2510

using namespace std;
typedef long long ll;
int n, m, kk, x, y, dis[A][A];
ll a[A], ans;

int main(int argc, char const *argv[]) {
	scanf("%d%d%d", &n, &m, &kk); kk++;
	for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);
	memset(dis, 0x3f, sizeof dis);
	for (int i = 1; i <= n; i++) dis[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		dis[x][y] = 1; dis[y][x] = 1;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	for (int i = 2; i <= n; i++) {
		if (dis[1][i] > kk) continue;
		for (int j = 2; j <= n; j++) {
			if (i == j) continue;
			if (dis[i][j] > kk) continue;
			for (int k = 2; k <= n; k++) {
				if (i == k or j == k) continue;
				if (dis[j][k] > kk) continue;
				for (int l = 2; l <= n; l++) {
					if (i == l or j == l or k == l) continue;
					if (dis[k][l] > kk or dis[l][1] > kk) continue;
					ans = max(ans, a[i] + a[j] + a[k] + a[l]);
				}
			}
		}
	}
	printf("%lld\n", ans);
}

比较特殊的数据点是当$k=0$时，也就是挑选的$4$个景点必须都相邻，直接通过$dfs$搜索所有的情况，如果遍历到了家（$1$号点）并且已经路过了$4$个不同的节点，这就是一条可行的路径，可以更新答案。$k=0$共有$9$个测试点，共$45$分。

#include <bits/stdc++.h>
#define A 2510

using namespace std;
int n, m, k, a[A], ans;
bool vis[A], mp[A][A];
void dfs(int now, int sum, int left) {
	if (now == 1 and left == 0) {
		ans = max(ans, sum);
		return;
	}
	else if (left == 0) return;
	for (int i = 1; i <= n; i++) {
		if (!mp[now][i] or vis[i]) continue;
		vis[i] = 1;
		dfs(i, sum + a[i], left - 1);
		vis[i] = 0;
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 2; i <= n; i++) cin >> a[i];
	while (m--) {
		int x, y;
		cin >> x >> y;
		mp[x][y] = 1; mp[y][x] = 1;
	}
	dfs(1, 0, 5);
	cout << ans << endl;
}

这个写法可以通过$k=0$的所有特殊情况，和第一个暴力结合一下，可以拿到$70$分。

#include <bits/stdc++.h>
#define A 2510

using namespace std;
typedef long long ll;
int n, m, kk, x, y, dis[A][A];
ll a[A], ans;
bool vis[A], mp[A][A];
void dfs(int now, ll sum, int left) {
	if (now == 1 and left == 0) {
		ans = max(ans, sum);
		return;
	}
	else if (left == 0) return;
	for (int i = 1; i <= n; i++) {
		if (!mp[now][i] or vis[i]) continue;
		vis[i] = 1;
		dfs(i, sum + a[i], left - 1);
		vis[i] = 0;
	}
}

int main(int argc, char const *argv[]) {
	scanf("%d%d%d", &n, &m, &kk);
	if (kk == 0) {
		for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);
		while (m--) {
			scanf("%d%d", &x, &y);
			mp[x][y] = 1; mp[y][x] = 1;
		}
		dfs(1, 0, 5);
		printf("%lld\n", ans);
		return 0;
	}
	kk++;
	for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);
	memset(dis, 0x3f, sizeof dis);
	for (int i = 1; i <= n; i++) dis[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		dis[x][y] = 1; dis[y][x] = 1;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	for (int i = 2; i <= n; i++) {
		if (dis[1][i] > kk) continue;
		for (int j = 2; j <= n; j++) {
			if (i == j) continue;
			if (dis[i][j] > kk) continue;
			for (int k = 2; k <= n; k++) {
				if (i == k or j == k) continue;
				if (dis[j][k] > kk) continue;
				for (int l = 2; l <= n; l++) {
					if (i == l or j == l or k == l) continue;
					if (dis[k][l] > kk or dis[l][1] > kk) continue;
					ans = max(ans, a[i] + a[j] + a[k] + a[l]);
				}
			}
		}
	}
	printf("%lld\n", ans);
}

我们要找的一个路径是$1\to A\to B\to C\to D\to 1$，可以发现其中$A$和$D$、$B$和$C$有一些共同之处：$A$和$D$的两端一定是起点$1$和一个其它的点，由于道路是双向的，所以可以说$A$、$D$这两个点是等价的；$B$和$D$的两端一定是非起点，可以说$B$、$C$这两个点是等价的。这样一来中间不同的四个点被压缩成了两个点。
用一个双重循环枚举$A$和$B$，$A$、$B$点的特征是$dis[1][A]<k$且$dis[A][B]<k$，同时满足条件的点$A$也对应着点$D$，点$B$对应着点$C$。对于所有的点$B$，找到所有符合条件的点$A$，符合条件的点$A$可能有很多，我们只需要存值最大的三个就可以。

为什么是存三个点？
对于路径$1\to A\to B\to C\to D\to 1$，假设枚举点$B$时找到了点$j$作为$A$点，枚举点$C$时找到了点$k$作为$D$点，那么$k=j$、$k=B$都是有可能发生的，所以要存三个点以防重复。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define A 2510
vector<int> e[A];
ll dis[A][A], ans, a[A];
bool vis[A];
int n, m, k;
void bfs(int start) {
	memset(vis, 0, sizeof vis); vis[start] = 1;
	queue<int> q; q.push(start);
	while (!q.empty()) {
		int fr = q.front(); q.pop();
		for (int i = 0; i < (int)e[fr].size(); i++) {
			int ca = e[fr][i];
			if (vis[ca]) continue;
			vis[ca] = 1;
			if (dis[start][ca] > dis[start][fr] + 1) {
				dis[start][ca] = dis[start][fr] + 1;
				q.push(ca);
			}
		}
	}
}
set<pair<ll, int> > s[A];

int main(int argc, char const *argv[]) {
	scanf("%d%d%d", &n, &m, &k); k++;
	for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);
	while (m--) {
		int x, y; scanf("%d%d", &x, &y);
		e[x].push_back(y); e[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			dis[i][j] = INT_MAX;
			if (i == j) dis[i][j] = 0;
		}
	for (int i = 1; i <= n; i++) bfs(i);
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= n; j++)
			if (i != j and dis[j][i] <= k and dis[1][j] <= k) {
				s[i].insert(make_pair(a[j], j));
				if (s[i].size() > 3) s[i].erase(s[i].begin());
			}
	}
	for (int i = 2; i <= n; i++)
		for (int j = 2; j <= n; j++) {
			if (dis[i][j] > k or i == j) continue;
			for (auto k : s[i]) {
				if (k.second == i or k.second == j) continue;
				for (auto l : s[j]) {
					if (l.second == i or l.second == j or l.second == k.second) continue;
					ans = max(ans, a[i] + a[j] + a[l.second] + a[k.second]);
				}
			}
		}
	cout << ans << endl;
}