資源限制
時間限制：100ms 記憶體限制：8.0MB
問題描述
樹的直徑
輸入格式
輸入的第一行包含一個整數n，表示樹中的點數，接下來n-1行，每行3個正整數，表示連同的兩點及邊的權值，
輸出格式
輸出1行，包含一個整數，表示樹的直徑，
樣例輸入
7
1 2 1
1 3 1
2 4 1
3 5 1
4 7 1
4 6 1
樣例輸出
5
資料規模和約定
n<10^5
思路：
樹的直徑：找相距最遠兩點之間的距離，即為樹的直徑，
從任一點出發，找到距離該點最遠的點 p1， p1 必定為直徑的一個端點， (跑一遍dfs)
從p1出發，找到距離p1最遠的點p2，p2必定為直徑的另一個端點，所以p1，p2兩點連線是相距最遠的兩點，即為樹的直徑， （再跑一遍dfs）
代碼：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1e5+10;
struct node{
int v,w;
node(int a,int b){v=a;w=b;}
};
int n,a,b,c,p1,maxlen=0;
vector<node> g[maxn]; //圖
bool vis[maxn]={false}; //是否走過
void dfs(int u,int dis)
{
if(dis>maxlen) //更新最遠距離和最遠點
{
maxlen=dis;
p1=u;
}
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].v;
int w=g[u][i].w;
if(!vis[v]) //沒訪問過
{
vis[v]=1;
dfs(v,dis+w);
vis[v]=0; //回溯
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n-1;i++)
{
cin>>a>>b>>c;
g[a].push_back(node(b,c));
g[b].push_back(node(a,c));
}
vis[1]=1;
dfs(1,0); //從任一點出發，這里從1出發
vis[1]=0;
maxlen=0; // 最遠距離
vis[p1]=1;
dfs(p1,0); //從p1出發，能最遠距離就是樹的直徑
vis[p1]=0;
cout<<maxlen;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/168381.html
標籤：其他