http://poj.org/problem?id=1985
题意是 给出一颗树 求一个以两个点为端点的最长距离
首先 存储数据 采用邻接表的方式存树
思路是 先从任意一个点出发 找离这个点最远距离的点a a一定是最长距离的一个端点(下面会证明) 再从a出发 同样找最长距离 这个距离就是答案
关于证明: 也就是对于任意点u，距离它最远的点v一定是最长路的一端。
如果u在最长路上，那么v一定是最长路的一端。可以用反证法：假设v不是最长路的一端，则存在另一点v’使得(u→v’)是最长路的一部分，于是len(u→v’) > len(u→v)。但这与条件“v是距u最远的点”矛盾。
如果u不在最长路上，则u到其距最远点v的路与最长路一定有一交点c，c一定是一个父节点(具体可以画图理解一下),且(c→v)与最长路的后半段重合，即v一定是最长路的一端。
求这个最长距离采用bfs的办法 具体看代码(有些地方有坑！标注了出来)
#include<bits/stdc++.h> using namespace std; int dis[100005],n,m,tot,first[100005],maxdis=-1; int point1,point2; struct data { int to; int next; int v; }; data edge[400005]; inline void add(int x,int y,int v) { tot++; edge[tot].to=y; edge[tot].v=v; edge[tot].next=first[x]; first[x]=tot; } void bfs(int node) { memset(dis,-1,sizeof(dis)); //别忘初始化 注意这个地方只能是-1 若是0会WA(我也不知道为什么) dis[node]=0,maxdis=-1; int now,vis; queue<int> dian; dian.push(node); while(!dian.empty()) { now=dian.front(); dian.pop(); for(int i=first[now];i;i=edge[i].next) { vis=edge[i].to; if(dis[vis]==-1) { dis[vis]=dis[now]+edge[i].v; if(maxdis<dis[vis]) { maxdis=dis[vis]; point1=vis; } dian.push(vis); } } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y,v; char dir; cin>>x>>y>>v>>dir; add(x,y,v); add(y,x,v); } bfs(1); bfs(point1); cout<<maxdis<<endl; return 0; }