思路
本图中f[x]表示x的子节点到x的最长距离,而非以x为顶点的最长路径.因为本题的路径是两条边,所以f[x]表示其中一条边的最大的值,f[y],f[z]同理,两条边加起来即为以u为顶点最长路径
注:本题的答案不一定为以u为顶点的路径,因为u到x,y,z的距离可能均为负数,所以答案可以是以x,y或者z为顶点的路径
本题采用dfs的方法来求解,所以是求解方式自下而上的
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010;
int h[N],w[2*N],ne[2*N],e[2*N],idx;
int ans;
void add(int a,int b,int c)
{
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u,int father)//father表示u的父节点,因为该图为无向图,并且迭代过程中不能回到父节点,所以要特殊标记.
{
int d1=0,d2=0;//因为题目描述中有:注意:路径中可以只包含一个点
//所以题目中的结果一定不为负数,负的路径由此可以忽略掉
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==father) continue;
int d=dfs(j,u)+w[i];//求出路径的长度
//d1,d2求出以该点为顶点的最长路径
if(d>=d1) d2=d1,d1=d;//最长路径和次长路径
else if(d>d2) d2=d;
}
ans=max(ans,d1+d2);
return d1;//返回当前点的f[x];
}
int main()
{
memset(h,-1,sizeof(h));
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)//n-1条边
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
add(a,b,w),add(b,a,w);
}
dfs(1,-1);
printf("%d",ans);
}
补充
我把dist给删了。。。改成返回d1,最大值也能过…我不是很明白这个变量的意义在哪里
其实删不删都无所谓,dist 与 d1 在过程中存的都是以x节点为根的树到其子节点路径长度的最大值, 但dist的意义侧重于长度,而d1的意义侧重于它是路径长度的最大值。
请问DFS为什么不能在下面比较的时候加上w[i]
e为什么要2N空间啊?
无向边
Orz
Orz
大佬讲的超级清晰 爱了爱了 点赞
大佬的头像超级清晰 爱了爱了 点赞 (:
好清晰,orz
本题采用bfs的方法来求解,所以是求解方式自下而上的
是dfs啦hh
谢谢指正
我有个问题,u为最高点的时候,如果d1,d2都小于0,d3大于0,此时只选择d3的话就不算一条完整的路径吧,路径不是要经过两个叶子结点吗
应该是我理解错了,路径只要是最远距离就行,不用考虑一定到叶子结点
你好,为啥随便选一个根节点点答案不会错,不用枚举一下根节点吗
用完了是无向图所以如何节点都可以是根节点,标记Fathe就是为了能自上而下的搜索
谢谢
我才发现错别字有点多,抱歉了,这里就重打一遍
因为是无向图,所以每个节点都可以是根节点,标记father是为了能够自上而下的搜索
谢谢,虽然读的有点别扭,但还是可以意会,哈哈哈~
这种解释好像说不通吧?
我的理解是这样,你可以把某个根节点当做一个钉子,其余节点看成线的节头,所有的边看成线,这样不管枚举的是哪个根节点,最终找到的一定是最长的那个直径。
随机选择一个点作为根节点,有两种情况,1:这个点在直径上,那么必然以他为根再加上最长和次长的两条边能够得到结果。2:这个点不在直径上,那么dfs下去必然能够找到直径上的一点,以那个点dfs最终能够得到结果。直径的距离最长,所以最后res的值就是直径的长度
好!
讲的是真的好