图解
一,介绍
二,思路
注意:
因为是无向图,所以每个点都可以是根节点,根节点没有向上的路径,叶子节点没有向下的路径
求up时,从根节点开始到子节点,再由子节点到孙子节点·····
建图时插入两次,清零操作
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010,M=2*N;
int h[N],ne[M],e[M],w[M],d1[N],d2[N],pm[N],idx,up[N];
void insert(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs_down(int u,int dad)
{
d1[u]=d2[u]=-0x3f3f3f3f;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==dad) continue;
int dist=dfs_down(j,u)+w[i];//u节点从j节点向下走的最大距离
if(dist>=d1[u])//更新最大值和次大值
{
d2[u]=d1[u];
d1[u]=dist;
pm[u]=j;//表示u向下经过j点时有最大距离
}
else if(dist>d2[u]) d2[u]=dist;
}
if(d1[u]==-0x3f3f3f3f) d1[u]=d2[u]=0;//如果值没有更新的话表示该节点为叶子节点(末节点)
return d1[u];//返回最大值
}
void dfs_up(int u,int dad)
//用父节点来更新子节点向上的距离
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==dad) continue;
if(pm[u]==j) up[j]=max(d2[u],up[u])+w[i];//如果u向下走的最大路径经过j的话,那么只能用次长距离
else up[j]=max(d1[u],up[u])+w[i];//不经过的话用最长的向下的路径
dfs_up(j,u);//用j更新j的子节点的最长向上距离
}
}
int main()
{
int n;
scanf("%d",&n);
memset(h,-1,sizeof(h));
for(int i=1;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
insert(a,b,c),insert(b,a,c);//无向图注意插入两次
}
dfs_down(1,-1);
dfs_up(1,-1);
int res=d1[1];//因为根节点没有向上的路径
for(int i=2;i<=n;i++)
res=min(res,max(up[i],d1[i]));
//因为本题数据中1<=c<=100000,没有负权边,所以不需要特判子叶节点的向下的路径不存在的情况
printf("%d",res);
return 0;
}
大佬,最后一张图的公式好像写错了,应该是$up[u] = d2[f] + w$
确实
佬
%%% or2
我想看的就是这个
d2[f] 不会也在当前节点 u 上吗?
向下的最长路径是按 f 的子节点枚举比较得出的,所以 最长路径和次长路径位于不同的子节点上
orz。
ora
太强了!!!
Orz
大佬 您画的图我完全看懂了 但是和这段代码有什么关系呀
if(pm[u]==j) up[j]=max(d2[u],up[u])+w[i];else up[j]=max(d1[u],up[u])+w[i];
被更新的左值也是up[j]呀 不应该是up[u]么?图上写的被更新的不都是up[u]么
由父更新子结点的up
嗯嗯 我后来理解了 谢谢!
好评
问一下这个1一定是根节点吗?题目没说吧
不一定
最后一张图写错了吧, 不是
up[u] = d2[f] + w
嘛你说的对
楼主楼主请问为什么dfs_down里要把d1[u]和d2[u]初始化成负无穷呢
判断叶子节点用的,因为叶子节点没有子节点,所以返回的应该为0
而且比较路径从大到小排序,一般都是用负无穷来作为初始值
谢谢楼主!
请问向下的情况2的话,如果最大距离和次大距离都经过了u呢,为什么次大距离就不会经过u啊
以u为根的子树,最终的出口是u,所以代表以u为根的子树对父结点f的贡献,如果最大距离在通过u过来的,那么次大的肯定不在以u为根的子树中了。
如果有负权边,需要判断叶子结点以及更新的最大边可能是负值,所以需要初始化为负无穷。但数据没有负权边,所以可以去掉