两次bfs即可
问题
给定一棵树,求最远的两点之间的距离。
两次bfs就行了,具体的证明有一点麻烦
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int n; int d[maxn]; bool vis[maxn]; struct Edge{ int v, weight; }; vector<Edge> G[maxn]; int bfs(int u){ for(int i=0; i<n; i++) d[i] = -1; memset(vis, 0, sizeof(vis)); d[u] = 0; queue<int> q; q.push(u); vis[u] = true; int long_dis = -1; while(!q.empty()){ int temp = q.front(); q.pop(); for(int i=0; i<G[temp].size(); i++){ Edge e = G[temp][i]; if(vis[e.v]) continue; else{ if(d[e.v]<d[temp]+e.weight){ d[e.v]=d[temp]+e.weight; q.push(e.v); long_dis = e.v; vis[e.v] = true; } } } } return long_dis; } void solve(){ int p = bfs(0); int q = bfs(p); int ans = -1; for(int i=0; i<n; i++){ ans = max(ans, d[i]); } printf("%d\n", ans); } int main() { while(cin>>n){ int u, v, weight; for(int i=0; i<n-1; i++){ cin>>u>>v>>weight; G[u].push_back(Edge{v, weight}); G[v].push_back(Edge{u, weight}); } solve(); } return 0; }
|
未解决的问题