P8817 题解
题目思路
45分
通过我们细致的观察，不难发现：当k=0时（即禁止转车），这道题直接就变成了一道纯DFS的题。从家开始进行深搜，直到搜索深度为5并且刚好搜索到家时停止。
以下是dfs函数
void dfs(int x,int sc,int step)
{
if(step==5)
{
if(x==1)
{
ans=max(ans,sc);
}
return;
}
for(int i=0;i<g[x].size();i++)
{
if(g[x][i]==1&&step<4) continue;
if(vis[g[x][i]]) continue;
vis[g[x][i]]=1;
dfs(g[x][i],sc+a[g[x][i]],step+1);
vis[g[x][i]]=0;
}
}
70分
经过我们那天才般的大脑的思考，我们可以想出一个天才思路：既然题目同意转车k次，那我们就把转车k次及以内能互相到达的两个点连起来当成有道路直接通达的两个点，把新图扔进刚刚的dfs里跑一遍就可以了，dfs甚至都不用修改。
以下为70分完整代码。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long n,m,k;
long long a[2505];
vector<long long> g[2505];
bool vis[2505];
long long ans;
long long lenth[2505][2505];
vector<long long> g2[2505];
void dfs(long long x,long long sc,int step)
{
if(step==5)
{
if(x==1)
{
ans=max(ans,sc);
}
return;
}
for(int i=0;i<g2[x].size();i++)
{
if(g2[x][i]==1&&step<4) continue;
if(vis[g2[x][i]]) continue;
vis[g2[x][i]]=1;
dfs(g2[x][i],sc+a[g2[x][i]],step+1);
vis[g2[x][i]]=0;
}
}
int main()
{
cin>>n>>m>>k;
memset(lenth,-1,sizeof(lenth));
for(int i=2;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
queue<long long> q;
q.push(i);
lenth[i][i]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int j=0;j<g[x].size();j++)
{
int y=g[x][j];
if(lenth[i][y]==-1)
{
lenth[i][y]=lenth[i][x]+1;
q.push(y);
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) continue;
if(lenth[i][j]<=k+1&&lenth[i][j]!=-1)
{
g2[i].push_back(j);
}
}
}
dfs(1,0,0);
cout<<ans;
return 0;
}
100分
乍一眼好像没法继续优化了，但是我们可以将旅行的过程分为三步：
1、从家到B景点，
2、从B景点到C景点，
3、从C景点到家。
整个旅行过程：
家–>A–>B–>C–>D–>家
对每个点 B，只保留权值最大的 3 个合法 A 点；对每个点 C，只保留权值最大的 3 个合法 D 点。
详细注释看代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
// n个点，m条边，题目给定k
long long n,m,k;
// a[i]：i号点的权值，1号点无权重
long long a[2505];
// 原图邻接表，存无向图
vector<long long> g[2505];
// vis数组代码里没有用到，可以删掉
bool vis[2505];
// 记录最终答案，四个点权值之和的最大值
long long ans;
// lenth[i][j]：点i到点j的最短路长度，-1代表不可达
long long lenth[2505][2505];
// best[i]：保存对于i来说，满足条件的权值最大的最多3个候选点
vector<long long> best[2505];
int main()
{
cin>>n>>m>>k;
// 初始化距离数组全部为-1，表示初始不可达
memset(lenth,-1,sizeof(lenth));
// 读入2~n号点的权值（题目1号点没有权）
for(int i=2;i<=n;i++)
{
cin>>a[i];
}
// 建无向图
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
// ========== BFS预处理任意两点最短路 ==========
// 对每个起点i，跑一次BFS，求出i到所有点的最短距离
for(int i=1;i<=n;i++)
{
queue<long long> q;
q.push(i);
lenth[i][i]=0; // 自己到自己距离为0
while(!q.empty())
{
int x=q.front();
q.pop();
// 遍历x所有相邻点
for(int j=0;j<g[x].size();j++)
{
int y=g[x][j];
// 如果y还没有被访问（距离为-1）
if(lenth[i][y]==-1)
{
lenth[i][y]=lenth[i][x]+1;
q.push(y);
}
}
}
}
// ========== 预处理每个点i的Top3候选点best[i] ==========
// best[i]存的是A：满足 dist(1,A)<=k+1 && dist(A,i)<=k+1 的权值最大的3个A
for(int i=2;i<=n;i++)
{
long long mx1=-1,mx2=-1,mx3=-1; // 第一、二、三大权值
int p1=0,p2=0,p3=0; // 对应权值的点编号
// 枚举所有可能的v作为候选A
for(int v=2;v<=n;v++)
{
if(v==i) continue; // A不能等于i
// 判断距离条件：1到v、v到i都可达，且长度≤k+1
if(lenth[1][v]!=-1&&lenth[v][i]!=-1&&lenth[1][v]<=k+1&&lenth[v][i]<=k+1)
{
// 更新前三名，类似维护排行榜
if(a[v]>mx1)
{
mx3=mx2; p3=p2;
mx2=mx1; p2=p1;
mx1=a[v]; p1=v;
}
else if(a[v]>mx2)
{
mx3=mx2; p3=p2;
mx2=a[v]; p2=v;
}
else if(a[v]>mx3)
{
mx3=a[v]; p3=v;
}
}
}
// 把存在的前3名加入best[i]，最多3个
if(p1!=0) best[i].push_back(p1);
if(p2!=0) best[i].push_back(p2);
if(p3!=0) best[i].push_back(p3);
}
// ========== 枚举B、C，查找最优A、D ==========
// 枚举B和C这两个中间点，要求dist(B,C) ≤ k+1
for(int B=2;B<=n;B++)
{
for(int C=2;C<=n;C++)
{
if(B==C) continue;
// B到C不可达或者距离超限，直接跳过
if(lenth[B][C]==-1||lenth[B][C]>k+1) continue;
// best[B]是B对应的候选A；best[C]是C对应的候选D
for(int i=0;i<best[B].size();i++)
{
for(int j=0;j<best[C].size();j++)
{
int A=best[B][i];
int D=best[C][j];
// 保证四个点A,B,C,D互不相同
if(A==B||A==C||A==D) continue;
if(D==B||D==C||D==A) continue;
// 计算当前四点权值总和，更新答案最大值
long long cur=a[A]+a[B]+a[C]+a[D];
ans=max(ans,cur);
}
}
}
}
cout<<ans;
return 0;
}
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/lch2011_yb/article/details/167128034
