复赛1：假期计划(holiday)
洛谷：P8817
OJ：P5943
我们考虑一条 1−a−b−c−d−1 的路径，n4 的枚举，暴力方法只得一部分分数，
直接贪心不行，a选权值大的，a的下一个选择b可能很小。
先预处理出对每个点 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，并确保每个选择的景点互不相同，且符合转车次数的限制。最终输出最高的分数。
满分：
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 75 76 77 78 79 80 81 82 83 84 85 86 87 | /**************************************************************** * Description: 2022提高组复赛第一题，假期计划 * Author: Alex Li * Date: 2023-10-02 19:39:50 * LastEditTime: 2023-10-05 11:03:09 ****************************************************************/ #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; } |