• 【题解】P8817 [CSP-S 2022] 假期计划（bfs，dfs）

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

    此题作为 CSP-S 的 T1，可以说是相当有难度了。感觉 T1 和 T2 换了个位置。(雾)

    我作为场外 VP 选手赛时此题只得了 95pts(洛谷民间数据)，靠着自己乱搞 dfs+剪枝水过去了 19 个点。

    这里记录一下这道题。

    题目链接

    题意概述

    给定一张 nn 个点 mm 条边的无向无权图，点有点权。需要找四个不同的点 a,b,c,d，使得 1−a−b−c−d−1 构成五段路径，且每段路径满足路径长度小于等于 k+1。现在要使得四个点权之和最大，求最大的点权和。

    思路分析

    这个 +1 看起来很难受，所以我们先将 k 直接 +1。

    为了方便说明这里自定义一些语言：

    • 若 x 到 y 的最短路径 ≤k 我们就称 x 到 y 可达。
    • 方便起见我们认为点 x 到 x 本身不可达、

    95pts 乱搞

    先讲述一下我乱搞 95pts 的做法。

    我当时看到这道题，，第一眼感觉正解应该想不到，然后就去想办法乱搞。

    最暴力的做法是，对于四个点从 1 开始 dfs，考虑每个点应该选什么，暴力枚举每个点然后最后判断是否符合条件，并更新答案即可。

    我们考虑如何优化。

    首先由于每段路径的长度都 ≤k，所以显然假如我们当前在 x，只有距离 x 最短路径 ≤k 的点才能拓展。那么我们可以从每个点首先预处理出来下一步可以到达的点。

    无权图上求最短路首先想到 bfs，这个显然可以枚举每个点然后预处理出来从每个点 i 到其它的点 j 的最短路 disi,j。单次 bfs 时间复杂度 O(n)，总时间复杂度 O(n2)，这个数据范围是 2500 级别的，可以随便过。

    然后预处理出来对于每个点 i 可达的点的集合 fx，然后每次更新下一个点的时候只在当前点的可达点集合中更新即可。

    另外还可以预处理出从 1 开始走可达的点，把它们打上标记。然后搜完三个点之后就在 fc 里面找看是否有打上标记的点，若打上标记则直接更新答案。

    考虑到 dfs 一定难逃剪枝，我们可以记录一下当前已经选过的点的点权和 sum 和图中最大点权 mx，当剩下未选的点数 (4−now)×mx≤当前答案 ans，那就说明一定不可行，直接剪掉即可。

    需要注意的一点是，为了保证四个点不同，我们必须定义一个 visi 数组表示 i 是否被选过，若被选过就不能再选了。

    然后这样做完，虽然看起来时间复杂度疑似 O(n4)，但实际上我们在各种剪枝优化中剪掉了很多没用的情况，所以实际上可以跑得很快。洛谷民间数据 95pts，除了 T 掉的那个点之外其它最慢的点也只跑了 200ms 多。

    正解

    我们发现在刚刚的暴力过程中，我们只要确定了前三个点，然后再只需要在第三个点 c 可达的点里面找被标记的点(1 可达的点)即可。

    那么这可以给我们思考正解带来启发：由于要权值和最大，当我们固定了 a,b,c 之后，我们直接在 c 可达的点中选择被标记的非 a,b 且权值最大的点即可。

    同理，由于环的对称性，可以发现当我们确定了 b,c,d 后，可以贪心的选择权值最大的 a。

    将上述两点结合起来，给了我们一种思路：

    我们只需要枚举 b,c，然后再将 b,c 可达的点按照权值从大到小排序，那么 a 就是 b 可达的点里面，且被标记的点中，非 c,d 的权值最大的点，d 就是 c 可达的点里面，且被标记的点中，非 a,b 的权值最大的点。

    那么我们怎么做呢？难道直接枚举 b,c 然后枚举 b 可达的点的集合和 c 可达的点的集合吗？

    emmm……仔细算一算复杂度发现最坏情况下其实趋近于 O(n4)……那你优化了个屁。(不是)

    仔细思考这样一件事情：

    我们对于 a 有以下几条限制：

    • 在 b 可达的点中；
    • 在被标记的点中(即 1 可达的点中)
    • 非 c,d；
    • 权值最大。

    实际上，我们可以把前两条放在一块来处理，即，我们通过 bfs 处理出来的集合 fx 可以不单单是每个点可达的点集，还可以让它满足同时是 1 可达的点，只要在原来的代码上稍作改动即可。(之后见代码)

    现在剩下最后两个条件。如果没有第三个条件。那么我们只需存 fx 中最大的直接更新即可。那么考虑到第三个条件，举个例子：假如当前 fx 中权值最大的点与 c 冲突，那就要考虑权值次大的点，假如这个次大的点又与 d 冲突那么就要考虑次次大点……所以实际上答案一定在 fx 的前三大中，我们只需要预处理出来每个 fx 中的前三大即可。

    到这里其实大体思路已经梳理完了。现在考虑如何写。

    如果我们直接分类讨论每个点会与哪个点冲突由于我们同时要考虑 a 和 d 这两个点的冲突情况，所以这里的细节非常复杂和麻烦。其实我们只需要枚举每个 fb 和 fc 的前三大然后直接更新答案即可。因为它只有最多 9 种情况，所以时间复杂度相当于 O(n2) 带个 9 的常数。

    代码实现

    95pts 乱搞做法

    1. //A
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define int long long
    8. using namespace std;
    9. const int maxn=2505;
    10. int a[maxn],dis[maxn][maxn],vis[maxn],book[maxn];
    11. int ans=0;
    12. int n,m,k,mx;
    13.  
    14. basic_string<int>edge[maxn],edge2[maxn];
    15.  
    16. inline int read()
    17. {
    18. 	int x=0,f=1;char ch=getchar();
    19. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    20. 	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    21. 	return x*f;
    22. }
    23.  
    24. void bfs(int x)
    25. {
    26. 	queue<int>q;
    27. 	q.push(x);
    28. 	while(!q.empty())
    29. 	{
    30. 		int now=q.front();
    31. 		q.pop();
    32. 		for(int nxt:edge[now])
    33. 		{
    34. 			if(dis[x][nxt])continue;
    35. 			dis[x][nxt]=dis[x][now]+1;
    36. 			q.push(nxt);
    37. 		}
    38. 	}
    39. }
    40.  
    41. void dfs(int x,int now,int sum)
    42. {
    43. 	if(sum+(4-now)*mxreturn ;//剪枝
    44. 	if(now==3)
    45. 	{
    46. 		for(int y:edge2[x])
    47. 		{
    48. 			if(book[y]&&vis[y]==0)//如果这个点没选过且在 1 可达点集中则更新答案。
    49. 			{
    50. 				ans=max(ans,sum+a[y]);
    51. 			}
    52. 		}
    53. 		return ;
    54. 	}
    55. 	for(int y:edge2[x])
    56. 	{
    57. 		if(vis[y])continue;
    58. 		vis[y]++;
    59. 		dfs(y,now+1,sum+a[y]);
    60. 		vis[y]=0;
    61. 	}
    62. }
    63.  
    64. signed main()
    65. {
    66. 	n=read();m=read();k=read();k++;
    67. 	for(int i=2;i<=n;i++)a[i]=read(),mx=max(mx,a[i]);
    68. 	for(int i=1;i<=m;i++)
    69. 	{
    70. 		int u,v;
    71. 		u=read();v=read();
    72. 		edge[u]+=v;
    73. 		edge[v]+=u;
    74. 	}
    75. 	for(int i=1;i<=n;i++)
    76. 	{
    77. 		bfs(i);//对每个点 bfs 预处理出来 dis
    78. 	}
    79. 	for(int i=1;i<=n;i++)
    80. 	{
    81. 		for(int j=2;j<=n;j++)
    82. 		{
    83. 			if(i==j)continue;
    84. 			if(dis[i][j]&&dis[i][j]<=k)
    85. 			{
    86. 				edge2[i]+=j;//这份代码中的 edge2[i] 表示的就是 i 的可达点的集合。
    87. 			}
    88. 		}
    89. 	}
    90. 	for(int v:edge2[1])book[v]++;//标记所有的 1 可达的点。
    91. 	dfs(1,0,0);
    92. 	cout<'\n';
    93. 	return 0;
    94. }

    正解

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define int long long
    8. using namespace std;
    9. const int maxn=2505;
    10. int ok[maxn][maxn],dis[maxn][maxn],w[maxn];//ok[i][j] 表示 i,j 是否可达。
    11. int n,m,k,ans;
    12.  
    13. vector<int>f[maxn];
    14.  
    15. basic_string<int>edge[maxn];
    16.  
    17. inline int read()
    18. {
    19. 	int x=0,f=1;char ch=getchar();
    20. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    21. 	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    22. 	return x*f;
    23. }
    24.  
    25. int cmp(int a,int b){return w[a]>w[b];}
    26.  
    27. void bfs(int x)
    28. {
    29. 	queue<int>q;
    30. 	q.push(x);
    31. 	dis[x][x]=0;
    32. 	while(!q.empty())
    33. 	{
    34. 		int now=q.front();
    35. 		q.pop();
    36. 		if(now!=x)
    37. 		{
    38. 			ok[x][now]++;
    39. 			if(x!=1&&ok[1][now])//如果起点不为 1 且是 1 可达的点。
    40. 			{
    41. 				f[x].push_back(now);
    42. 				sort(f[x].begin(),f[x].end(),cmp);//按边权从大到小排序。
    43. 				if(f[x].size()>3)f[x].pop_back();//只保留前三大。
    44. 			}
    45. 		}
    46. 		if(dis[x][now]>=k)continue;//如果当前 dis 已经大于等于 k 就没必要再用，因为不可能更新。
    47. 		for(int nxt:edge[now])
    48. 		{
    49. 			if(dis[x][nxt]!=-1)continue;
    50. 			dis[x][nxt]=dis[x][now]+1;
    51. 			q.push(nxt);
    52. 		}
    53. 	}
    54. }
    55.  
    56. signed main()
    57. {
    58. 	memset(dis,-1,sizeof(dis));
    59. 	n=read();m=read();k=read();k++;
    60. 	for(int i=2;i<=n;i++)w[i]=read();
    61. 	for(int i=1;i<=m;i++)
    62. 	{
    63. 		int u,v;
    64. 		u=read();v=read();
    65. 		edge[u]+=v;
    66. 		edge[v]+=u;
    67. 	}
    68. 	for(int i=1;i<=n;i++)bfs(i);//这里的 bfs 处理的是 f[x]
    69.     //暴力枚举每个 b，c，并对每对 b，c 枚举可能的 9 种答案。
    70. 	for(int b=2;b<=n;b++)
    71. 	{
    72. 		for(int c=2;c<=n;c++)
    73. 		{
    74. 			if(!ok[b][c])continue ;//b 必须可达 c。
    75. 			for(int a:f[b])
    76. 			{
    77. 				for(int d:f[c])
    78. 				{
    79. 					if(a!=c&&b!=d&&a!=d)//a 显然本身不可能与 b,d 不可能与 c 冲突。
    80. 					{
    81. 						ans=max(ans,w[a]+w[b]+w[c]+w[d]);//更新答案。
    82. 					}
    83. 				}
    84. 			}
    85. 		}
    86. 	}
    87. 	cout<'\n';
    88. 	return 0;
    89. }
  • 相关阅读:
    C++面试连环问-STL
    使用Kube-prometheus部署Prometheus
    什么是云计算中的资源调度，解释资源调度的挑战和算法
    torch实现Gated PixelCNN
    小米软件开发二面和中兴软开一面
    SpringBoot——》引入Redis
    Java版电子招投标管理系统源码-电子招投标认证服务平台-权威认证
    【数论】质数
    RISC-V 编译环境搭建：riscv-gnu-toolchain 和 riscv-tools
    【学习笔记39】获取DOM标签对象
  • 原文地址：https://blog.csdn.net/m0_46222454/article/details/127680427