Hlg 树的直径.cpp

题意：
　　给出一棵树..求出一条路..使得别的点到这条路径的距离最长的最短..

输入：
　　　　n 表示树上有n个点..
　　　　u v w 表示u和v这两个相连的点的边权值为w

思路：
　　3次广搜..
　　第一次从任意一个点找最长的路径~这个路径的终点就是要求的路的终点..
　　第二次从终点开始找最长的路径..这时候找到的路径就是最后的路了..
　　然后从这个队列往外遍历相连的路..
　　这时候找出来的最长的距离就是要求的答案..

Tips：
　　因为加边的时候是双向边..
　　所以边的数组应该开两倍大..
　　pre 数组要注意~~~~

Code：

View Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <stdio.h>
  4 using namespace std;
  5 #define clr(x) memset(x, 0, sizeof(x))
  6 
  7 const int MAXN = 100010;
  8 
  9 struct Edge
 10 {
 11     int to;
 12     int next;
 13     int w;
 14 }edge[MAXN*2];
 15 int tot;
 16 int head[MAXN];
 17 
 18 void add(int s, int u, int w) {
 19     edge[tot].to = u;
 20     edge[tot].next = head[s];
 21     edge[tot].w = w;
 22     head[s] = tot++;
 23 
 24     edge[tot].to = s;
 25     edge[tot].next = head[u];
 26     edge[tot].w = w;
 27     head[u] = tot++;
 28 }
 29 
 30 struct Node
 31 {
 32     int num;
 33     int dis;
 34 }que[MAXN];
 35 
 36 bool vis[MAXN];
 37 int rd[MAXN];
 38 int bfs()
 39 {
 40     Node tmp, tmp1;
 41     int pre[MAXN];
 42     int tmps, ma = 0, s, e, ans = 0;
 43     clr(pre);
 44     int front = 0, rear = 0;
 45     clr(vis);
 46     tmp.num = 1;
 47     tmp.dis = 0;
 48     que[rear++] = tmp;
 49     vis[1] = true;
 50     while(front < rear) {
 51         tmp = que[front++];
 52         tmps = tmp.num;
 53         for(int i = head[tmps]; i; i = edge[i].next)
 54         if(!vis[edge[i].to]) {
 55             tmp1.num = edge[i].to;
 56             tmp1.dis = edge[i].w + tmp.dis;
 57             que[rear++] = tmp1;
 58             vis[edge[i].to] = true;
 59             if(ma < tmp1.dis) {
 60                 ma = tmp1.dis;
 61                 e = tmp1.num;
 62             }
 63         }
 64     }
 65 
 66     ma = front = rear = 0;
 67     clr(vis);
 68     tmp.num = e;
 69     tmp.dis = 0;
 70     que[rear++] = tmp;
 71     vis[e] = true;
 72     while(front < rear) {
 73         tmp = que[front++];
 74         tmps = tmp.num;
 75         for(int i = head[tmps]; i; i = edge[i].next)
 76         if(!vis[edge[i].to]) {
 77             tmp1.num = edge[i].to;
 78             tmp1.dis = edge[i].w + tmp.dis;
 79             vis[edge[i].to] = true;
 80             que[rear++] = tmp1;
 81             pre[tmp1.num] = tmps;
 82             if(ma < tmp1.dis) {
 83                 s = tmp1.num;
 84                 ma = tmp1.dis;
 85             }
 86         }
 87     }
 88 
 89     ma = front = rear = 0;
 90     clr(vis);
 91     tmp.num = s;
 92     tmp.dis = 0;
 93     que[rear++] = tmp;
 94 //printf("%d===>", s);
 95     while(pre[s]) {
 96 //printf("%d==>", pre[s]);
 97         tmp.num = pre[s];
 98         tmp.dis = 0;
 99         que[rear++] = tmp;
100         vis[s] = true;
101         s = pre[s];
102     }
103 //printf("%d", e);
104 //puts("");
105     vis[e] = true;
106     while(front < rear) {
107         tmp = que[front++];
108         tmps = tmp.num;
109         for(int i = head[tmps]; i; i = edge[i].next)
110         if(!vis[edge[i].to]) {
111             tmp1.num = edge[i].to;
112             tmp1.dis = edge[i].w + tmp.dis;
113             que[rear++] = tmp1;
114             vis[tmp1.num] = true;
115             if(tmp1.dis > ma) {
116                 ma = tmp1.dis;
117             }
118         }
119     }
120     return ma;
121 }
122 
123 
124 int main()
125 {
126     int i, j, k;
127     int n, a, b;
128     int u, v, w;
129     while(scanf("%d", &n) != EOF) {
130         if(n == 0) break;
131 
132         tot = 1;
133         clr(head);
134         for(i = 0; i < n-1; ++i) {
135             scanf("%d %d %d", &u, &v, &w);
136             add(u, v, w);
137         }
138 
139         printf("%d\n", bfs());
140     }
141     return 0;
142 }

题目链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1460