P8817 [CSP-S 2022] 假期计划 题解

发表于 分类于

本文迁移自洛谷原文。

这里是 [CSP-S 2022]假期计划 的另类做法。

  • 先暴力bfs把所有能在 $k$ 步内达到的点互相连边，复杂度 $O(n^2)$

  • 然后随机染色。对于每个点，随机染上 $1\dots4$ 这四种颜色中的任意一种，然后就相当于选出有4个颜色不同的点的包含点1的环。这样就避免了重复经过某个点的情况。

  • 显然这是原问题的弱化版，每次有 $(\frac{2}{4^4})$ 的可能性对，随个 $200$ 次就能过洛谷的民间数据了。

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
//start coding at 2:35
//finish coding at 2:47
//finish debuging at 2:55
//Code by paulzrm
/*
虽千万人逆我之我仍执着
侠客行遍九州恩仇奔波
刀光剑影里是谁的明眸粲粲如星火
纵使我双掌倚天苍龙俘获
奈何降不住这人心如魔
所谓天下第一 怎囿我天高海阔
*/
/*
此战 我战与我！
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=2505;
vector<int>g[mxn],ng[mxn];
ll n,m,k;
ll a[mxn];
int dist[mxn][mxn];
inline void bfs(int x){
	queue<int>q;for(;q.size();)q.pop();
	q.push(x);memset(dist[x],63,sizeof(dist[x]));dist[x][x]=0;
	for(;q.size();){
		int u=q.front();q.pop();
		for(int v:g[u])if(dist[x][v]>dist[x][u]+1){
			dist[x][v]=dist[x][u]+1;
			q.push(v);
		}
	}
}
int col[mxn];
ll dp[mxn],ans;
inline ll dfs(int x,int d){
	if(dp[x]!=-1)return dp[x];
	dp[x]=-5000000000000000000ll;
	if(d==4){
		if(dist[1][x]<=k+1)dp[x]=a[x];
		else dp[x]=-5000000000000000000ll;
		return dp[x];
	}
	for(int y:ng[x])
		if(col[y]==d+1)
			dp[x]=max(dp[x],dfs(y,d+1)+a[x]);
	return dp[x];
}
int main(){
	ios_base::sync_with_stdio(false);
	srand(1145141);
	cin>>n>>m>>k;
	for(int i=2;i<=n;++i)cin>>a[i];
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;++i)bfs(i);
	for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(dist[i][j]<=k+1){
		ng[i].push_back(j);
		ng[j].push_back(i);
	}
	for(int ee=0;ee<200;++ee){
		if(rand()%3==1)rand();
		for(int i=2;i<=n;++i)col[i]=rand()%4+1;
		memset(dp,-1,sizeof(dp));
		dfs(1,0);
		ans=max(ans,dp[1]);
	}
	cout<<ans<<endl;
	return 0;
}

upd：这份没有卡时的代码在官方数据下获得了整整 65pts，但我们可以通过一个 clock() 来进行卡时，获得 100pts。

Code：

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=2505;
vector<int>g[mxn],ng[mxn];
ll n,m,k;
ll a[mxn];
int dist[mxn][mxn];
inline void bfs(int x){
	queue<int>q;for(;q.size();)q.pop();
	q.push(x);memset(dist[x],63,sizeof(dist[x]));dist[x][x]=0;
	for(;q.size();){
		int u=q.front();q.pop();
		for(int v:g[u])if(dist[x][v]>dist[x][u]+1){
			dist[x][v]=dist[x][u]+1;
			q.push(v);
		}
	}
}
int col[mxn];
ll dp[mxn],ans;
inline ll dfs(int x,int d){
	if(dp[x]!=-1)return dp[x];
	dp[x]=-5000000000000000000ll;
	if(d==4){
		if(dist[1][x]<=k+1)dp[x]=a[x];
		else dp[x]=-5000000000000000000ll;
		return dp[x];
	}
	for(int y:ng[x])
		if(col[y]==d+1)
			dp[x]=max(dp[x],dfs(y,d+1)+a[x]);
	return dp[x];
}
int main(){
    clock_t st=clock();
	ios_base::sync_with_stdio(false);
	srand(1919810);
	cin>>n>>m>>k;
	for(int i=2;i<=n;++i)cin>>a[i];
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;++i)bfs(i);
	for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(dist[i][j]<=k+1){
		ng[i].push_back(j);
		ng[j].push_back(i);
	}
	for(int ee=0;ee<10000;++ee){
	    if(clock()-st>1.98*CLOCKS_PER_SEC)break;
		if(rand()%3==1)rand();
		for(int i=2;i<=n;++i)col[i]=rand()%4+1;
		memset(dp,-1,sizeof(dp));
		dfs(1,0);
		ans=max(ans,dp[1]);
	}
	cout<<ans<<endl;
	return 0;
}