CCF认证201503-4网络延时——深度优先遍历和动态规划
欢迎访问我的CCF认证考试题解目录哦 https://blog.****.net/ri*qi/article/details/83385502
题目描述
算法设计
这是一道求解树的最长路径的问题。有两种方法:深度优先遍历和动态规划。
深度优先遍历
将树看成无环连通无向图,从任意一个顶点(我用的是根结点)u
出发用BFS或者DFS搜索到距离根节点最远的结点v1
,然后从结点v1出发再次使用BFS或者DFS得到的距离最远的结点v2
。v1
与v2
之间的路径长度就是树的最长路径长度。
C++代码
#include<bits/stdc++.h>
using namespace std;
vector<int>tree[20005];//存储整棵树
int n,m,a,ansV=-1,ansLevel=0;//ansV表示距离最远的结点编号,ansLevel表示最远距离
bool visit[20005];//标记每个节点是否已被访问
void DFS(int v,int level){//深度优先遍历
visit[v]=true;
if(level>ansLevel){
ansLevel=level;
ansV=v;
}
for(int i:tree[v])
if(!visit[i])
DFS(i,level+1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=2;i<=n+m;++i){
scanf("%d",&a);
tree[a].push_back(i);
tree[i].push_back(a);//将树的边存储为无向边
}
DFS(1,0);//第一次深度优先遍历
memset(visit,0,sizeof(visit));
DFS(ansV,0);//二次遍历
printf("%d",ansLevel);
return 0;
}
动态规划
定义两个一维数组dp1
,dp2
,dp1[i]
表示以结点i
为根结点到叶结点的最大距离;dp2[i]
表示以结点i
为根结点且经过结点i
的最长路径长度。容易得到状态转移方程:
假设距离结点i
距离前两大的两个结点分别为u
、v
,则
C++代码
#include<bits/stdc++.h>
using namespace std;
vector<int>tree[20005];//存储整棵树
int n,m,a;
int dp1[20005],dp2[20005];
void DP(int v){//深度优先遍历
int max1=0,max2=0;
for(int i:tree[v]){
DP(i);
if(dp1[i]+1>max1){//计算到根结点v到叶子结点的最远距离
max2=max1;
max1=dp1[i]+1;
}else if(dp1[i]+1>max2)//计算到根结点v到叶子结点的第二远距离
max2=dp1[i]+1;
}
dp1[v]=max1;
dp2[v]=max1+max2;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=2;i<=n+m;++i){
scanf("%d",&a);
tree[a].push_back(i);
}
DP(1);
printf("%d",*max_element(dp2+1,dp2+n+m+1));//dp2中最大值即为所求
return 0;
}