复赛一：假期计划(holiday)

信息学奥赛历年真题 2022年NOIP提高组真题复赛一：假期计划(holiday)

洛谷：P8817
OJ：P5943

方案一：45分

只计算k=0的情况，也就是假设没有跳跃，有DFS就可以。

代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-10-08 03:52:31
 * 最后修改: 2025-10-08 15:18:16
 * 文件描述: 【22CSPS提高组】假期计划(holiday)  k=0的情况
****************************************************************/

#include <bits/stdc++.h>
#include <vector>
using namespace std;
long long a[2501]; //a[i] 表示景点 i 的分数。
long long maxs=0;
vector<int>   b[2501];//b[i] 表示与节点 i 直接相连的邻接点（邻接表）。
bool  f[2501];
void dfs(int x,int deep, long long sum){
    if(deep==5){
        if(x==1)maxs=max(maxs,sum);
        return ;
    }
    if(f[x])return ;
    f[x]=1;
    for(int i=0;i<b[x].size();i++){
        dfs(b[x][i],deep+1,sum+a[x]);
    }
      f[x]=0;
}

int main(){
   int n,m,k;
    cin>>n>>m>>k;
    if(k==0){
    for(int i=2;i<=n;i++)cin>>a[i];//注意编号从 2 开始（a[1] = 0）。
    for(int i=0;i<m;i++){// 记录无向图
        int u,v;
        cin>>u>>v;
        b[u].push_back(v);
        b[v].push_back(u);
    }
    dfs(1,0,0);// 从家出发，走0步，得分0
    cout<<maxs;
}
    return 0;
}

方案二：70分

1. 建图：

使用邻接表 b[u] 构建图，记录每个节点 u 与其相邻的节点 v。

2. 多源 BFS 预处理：

对于每个节点 x，使用 BFS 构建一张从 x 出发，最多转车 k 次能到达的所有节点集合，保存在 c[x] 中。
这样我们就可以在 DFS 搜索路径时，只考虑合法路径（每段最多转车 k 次）——大大加速搜索。

3. DFS 路径搜索：

从家（节点 1）出发，用 DFS 搜索深度为 5 的路径（走 5 段路），路径中不能重复节点（除家可以出现两次），每次只走 c[x] 中可达节点。
在第 5 步（deep == 5）时，检查是否回到了家（x == 1），如果是就更新最大得分。

代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-10-08 03:52:31
 * 最后修改: 2025-10-08 15:30:41
 * 文件描述: 【22CSPS提高组】假期计划(holiday)  k!=0的情况
****************************************************************/

#include <bits/stdc++.h>
#include <queue>
#include <vector>
using namespace std;
long long a[2501],maxs=0;
vector<int> b[2501],c[2501];// b[i] 是原图邻接表，c[i] 是最多转 k 次能从 i 到达的点集合
bool  f[2501];

void bfs(int x, int k) {
    bool h[2501] = {0};                       // 局部访问标记，防止在 BFS 中重复走节点
    queue<pair<int,int>> q;                      // 队列中存 (当前节点, 当前深度)
    q.push({x, -1});                             
    h[x] = 1;

    while (!q.empty()) {
        int deep = q.front().second;             // 到达当前节点的转车次数
        int node = q.front().first;
        q.pop();

        if (deep >= k) continue;                 // 已达最大转车次数限制，停止继续扩展

        for (int i = 0; i < b[node].size(); i++) {
            int to = b[node][i];
            if (!h[to]) {
                c[x].push_back(to);              // x 在最多转 k 次内可达 to
                q.push({to, deep + 1});
                h[to] = 1;
            }
        }
    }
}

void dfs(int x,int deep, long long sum){
    if(deep==5){
        if(x==1)maxs=max(maxs,sum);
        return ;
    }
    if(f[x])return ;
    f[x]=1;
    for(int i=0;i<c[x].size();i++){
        dfs(c[x][i],deep+1,sum+a[x]);
       
    }
     f[x]=0;
}

int main(){
   int n,m,k;
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++)cin>>a[i];
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        b[u].push_back(v);
        b[v].push_back(u);
    }
    for(int i=1;i<=n;i++)bfs(i,k);
    dfs(1,0,0);
    cout<<maxs;
    return 0;
}

方案三：满分

先预处理出对每个点 i ，同时满足到 i 和到 1 号点距离不超过 k+1 的点中权值前三大的点。为什么是前三大？因为接下来要枚举中间两个点 B，C ，然后 A 从 B 预处理的前三大点中选，D 从 C 预处理的前三大点中选，为了避免 A 和 C,D 重复以及 D 和 A,B 重复。

输入处理：

首先读取了 n（节点数），m（双向直达的点对数量），和 k（每段行程最多的转车次数）。节点编号 1 是家，编号 2~n 是景点。
使用 a[] 数组存储每个景点的分数（编号从 2 开始）。编号为 1 的家不需要存储分数。
然后读取 m 条边，表示哪些点之间有直达的公交线路。

BFS 距离计算：

bfs(int s) 函数用来从某个节点 s 出发，计算它到所有其他节点的最短路径，最多转车 k 次。
通过宽度优先搜索（BFS）来计算到每个点的最短距离，存储在二维数组 d[s][i] 中，表示从节点 s 到节点 i 的最短距离（转车次数）。

最大分数的选择：

对于每个景点 i，程序通过 BFS 计算它与其他景点之间的最短距离，然后选出分数最高的三个点，存储在 b[i][0], b[i][1], b[i][2] 中。这个过程会跳过与 i 自身相同的点或距离不满足条件的点。

主函数逻辑：寻找最大分数：

主体逻辑是通过遍历所有可能的景点组合 (i, j) 来计算总分数，分别尝试选择景点 A, B, C, D，并确保每个选择的景点互不相同，且符合转车次数的限制。最终输出最高的分数。

满分：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-10-02 19:39:50
 * 最后修改: 2025-10-17 19:09:22
 * 文件描述: [CSP-S 2022] 假期计划
****************************************************************/

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long LL;
const int N=2505;

int n,m,k;
LL a[N]; // 结点的权值,范围是10^18次方，所以需要LL型
vector<int> G[N];//有n个结点m条边, n最大取250，用动态数组存图
int d[N][N];//各点之间的距离，k是条件
int b[N][3];//某点前三大的权值结点

void bfs(int s){  // 求出各点到s点的距离
    for(int i=1;i<=n;i++)d[s][i]=-1;
    queue<int> q;
    q.push(s),d[s][s]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        if(d[s][u]==k)break;
        for (auto v:G[u]){
            if(d[s][v]==-1)d[s][v]=d[s][u]+1;
            q.push(v);    
        }
    }
}

 int main(){
    cin>>n>>m>>k;
    k++;
    for (int i =2; i <=n; i++){
        cin>>a[i];
    }
    while(m--){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(1);
    for (int i =2; i <=n; i++){
        bfs(i);//宽搜出每个i点与其它结点的权值
        int &x1=b[i][0],&x2=b[i][1],&x3=b[i][2];
        for (int j = 2; j <=n; j++){
            if(i==j)continue;
            if(d[1][j]!=-1&&d[i][j]!=-1){//选出每个结点前三大权值的结点(不超过K+1)
                if(a[j]>a[x1]){
                    x3=x2,x2=x1,x1=j;
                }else if(a[j]>a[x2]){
                    x3=x2,x2=j;
                }else if(a[j]>a[x3]){
                    x3=j;
                }
            }
        }
        
    }
    LL ans=0;
    //遍历B、C，然后在B、C后再遍历A、D，只是A、D是在B、C权值最大的三个点里面。所以遍历范围小了。
    for (int i =2; i <=n; i++){
        for (int j = i+1; j <=n; j++){
            if(d[i][j]==-1)continue;
            for (int k1 =0; k1 <3; k1++){
                for (int k2 = 0; k2< 3; k2++){
                    int x=b[i][k1],y=b[j][k2];
                    if(x==0||y==0||x==y||x==i||x==j||y==i||y==j)continue;
                    ans=max(ans,a[i]+a[j]+a[x]+a[y]);
                }
                
            }
            
        }
        
    }
    
cout<<ans;
return 0;

 }

Previous Lesson

Back to Lesson

Next Topic