首页 > 代码库 > hdu--2196--树上某点到其余结点的最远距离
hdu--2196--树上某点到其余结点的最远距离
这题 很多人都是用树形dp进行2次dfs做的...
我看了他们的解题报告 并没有完全搞懂=-= 我太白痴了 伤..
这边 我的解法 利用了一个很重要的性质---树的直径--树上任意两点间的最远距离
而同时 将这个直径上的两点x , y确定后 那么 整个树上结点的dist[ i ]也就可以确定了
max( dist[i][x] , dist[i][y] ) 要么是到x的距离 要么是到y的距离
至于 怎么找出这个直径呢？
这也是个要记住的地方 我们可以任意确定一个根结点开始bfs 得到距离它最远的结点编号 那么这个结点就是 树中直径的某一端点
然后再bfs这个得到的端点 可以得到直径的另一端点 最后Bfs这个端点 同时在这对于直径端点的bfs中 分别用不同数组记录下距离
最后用max输出
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 7 int cnt; 8 const int size = 10010; 9 struct data10 {11 int to;12 int val;13 int next;14 }node[size*2];15 int head[size];16 int dist1[size];17 int dist2[size];18 bool vis[size];19 20 void init( )21 {22 memset( head , -1 , sizeof(head) );23 memset( dist1 , 0 , sizeof(dist1) );24 memset( dist2 , 0 , sizeof(dist2) );25 }26 27 void addEdge( int from , int to , int dist )28 {29 node[cnt].to = to;30 node[cnt].val = dist;31 node[cnt].next = head[from];32 head[from] = cnt ++;33 }34 35 int bfs( int num , int* dist )36 {37 int ans , now , len;38 len = -1;39 memset( vis , false , sizeof(vis) );40 queue<int>q;41 q.push(num);42 vis[num] = 1;43 while( !q.empty() )44 {45 now = q.front();46 q.pop();47 if( dist[now] > len )48 {49 len = dist[now];50 ans = now;51 }52 for( int i = head[now] ; ~i ; i = node[i].next )53 {54 int to = node[i].to;55 int val = node[i].val;56 if( !vis[to] )57 {58 vis[to] = true;59 q.push(to);60 dist[to] = dist[now] + val;61 }62 }63 }64 return ans;65 }66 67 int main()68 {69 cin.sync_with_stdio(false);70 int n , x , y , point;71 while( cin >> n )72 {73 cnt = 0;74 init( );75 for( int i = 2 ; i<=n ; i++ )76 {77 cin >> x >> y;78 addEdge( i , x , y );79 addEdge( x , i , y );80 }81 point = bfs( 1 , dist1 );82 memset( dist1 , 0 , sizeof(dist1) );83 point = bfs( point , dist1 );84 point = bfs( point , dist2 );85 for( int i = 1 ; i<=n ; i++ )86 {87 cout << max( dist1[i] , dist2[i] ) << endl;88 }89 }90 return 0;91 }
today:
人们说
当遇上你的挚爱时
时间会暂停
那是真的
但人们没有告诉你
当时针再度恢复转动
它会无比飞快
让人无法追上
hdu--2196--树上某点到其余结点的最远距离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。