题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <climits>
#define N 10010
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,ans=INT_MAX;
int h[N],e[N*2],w[N*2],ne[N*2],idx;
int up[N];//up[i]表示点i向上走的最远距离
int down1[N],down2[N];//down1[i]表示点i向下走的最远距离,down2[i]表示点i向下走的次远距离
int p[N];//p[u]=j表示从u往下走是最长路径的儿子编号为j
//ans=min(max(up[1~n],down[1~n]))
//更新up: 1.若j位于down1[u]上,即最长路上,则up[j]=w[i]+max(up[u],down2[u])
// 2.若j不位于down1[u]上,则up[j]=w[i]+max(up[u],down1[u])
//up的更新应在dfs之前
//更新down:1.down1[j]+w[i]>=down1[u]-->down2[u]=down1[u],down1[u]=down1[j]+w[i]
// 2.down1[j]+w[i]>down2[u]-->down2[u]=down1[j]+w[i]
//down的更新应在dfs之后
void add(int a,int b,int c)
{
e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++;
}
//计算down1,down2时,是用子节点的down计算父节点的down,故先递归,再计算
void dfs_down(int u,int fa)//先遍历u向下走的最远距离
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs_down(j,u);
if(down1[j]+w[i]>=down1[u]) down2[u]=down1[u],down1[u]=down1[j]+w[i],p[u]=j;
else if(down1[j]+w[i]>down2[u]) down2[u]=down1[j]+w[i];
}
}
//而计算up时,是用父节点的up计算子节点的up,故先计算,再递归
void dfs_up(int u,int fa)//再遍历u向上走的最远距离
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
if(p[u]==j) up[j]=w[i]+max(up[u],down2[u]);//j位于u的最长路上,则用up[u]和down2[u]更新
else up[j]=w[i]+max(up[u],down1[u]);//不在最长路,即可用down1[u]更新
dfs_up(j,u);
}
ans=min(ans,max(up[u],down1[u]));//取最小值
}
//递归路径永远都是先父后子
//总结:用父节点信息推出子节点信息,要先计算,后递归
// 用子节点信息推出父节点信息,要先递归,后计算
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<n;i++)
{
int a,b,w;
cin>>a>>b>>w;
add(a,b,w);
add(b,a,w);
}
dfs_down(1,-1);
dfs_up(1,-1);
cout<<ans;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla