P8817 [CSP-S 2022] 假期计划 的另类做法
RedLycoris · · 题解
这里是 [CSP-S 2022]假期计划 的另类做法。
-
先暴力bfs把所有能在
k 步内达到的点互相连边，复杂度O(n^2) -
然后随机染色。对于每个点，随机染上
1\dots4 这四种颜色中的任意一种，然后就相当于选出有4个颜色不同的点的包含点1的环。这样就避免了重复经过某个点的情况。 -
显然这是原问题的弱化版，每次有
(\frac{2}{4^4}) 的可能性对，随个200 次就能过洛谷的民间数据了。
//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：
#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;
}