今天继续饶齐博客
http://poj.org/problem?id=1985
具体解法: 首先从树上任意一个点a出发, (BFS)找出到这个点距离最远的点b.
然后在从b点出发(BFS)找到距离b点最远的点c. 那么bc间的距离就是树的直径.
证明:
1. a点在最长路上时, b点一定是最长路的一个端点.
反证:如果b不是端点, 那么最长路的前半段+从a到b的这段必然比原先的最长路更长, 这样就矛盾了.
2. a点不在最长路上时, a->b一定与最长路有交点(这是一个结论), 且a->b的后半段一定与最长路重合(如果不重合,那么明显又来了一条比最长路还长的路). 即b一定是最长路的端点.
程序实现用的是邻接表来表示树结构.
Head[i]==j 表示与i结点连接的边组成了一条链表, 其中第j条边是这条链的头一个元素, 接着通过j可以找到剩余的(与i连接的)边.
Edge是用来表示每条边的结构.
BFS返回从s结点能走到的最远的点的编号
AC代码:
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<queue>
- using namespace std;
- const int maxn=50000+5;
- const int maxm=100000+5;
- //有向边
- struct Edge
- {
- Edge(){}
- Edge(int to,int cost,int next):to(to),cost(cost),next(next){}
- int to; //边尾部
- int cost; //边距离
- int next; //指向下条边
- }edges[maxm];
- int cnt=0; //边总数
- int head[maxn];//头结点
- //添加两条有向边
- void AddEdge(int u,int v,int cost)
- {
- edges[cnt]=Edge(v,cost,head[u]);
- head[u]=cnt++;
- edges[cnt]=Edge(u,cost,head[v]);
- head[v]=cnt++;
- }
- //距离
- int dist[maxn];
- //BFS返回从s出发能到达的最远点编号
- int BFS(int s)
- {
- int max_dist=0;
- int id=s;
- queue<int> Q;
- memset(dist,-1,sizeof(dist));
- dist[s]=0;
- Q.push(s);
- while(!Q.empty())
- {
- int u=Q.front(); Q.pop();
- if(dist[u]>max_dist)
- max_dist=dist[id=u];
- for(int i=head[u]; i!=-1; i=edges[i].next)
- {
- Edge &e=edges[i];
- if(dist[e.to]==-1)
- {
- dist[e.to]=dist[u]+e.cost;
- Q.push(e.to);
- }
- }
- }
- return id;
- }
- int main()
- {
- int n,m;
- while(scanf("%d%d",&n,&m)==2)
- {
- cnt=0;
- memset(head,-1,sizeof(head));
- int u,v,cost;
- char c;
- for(int i=1;i<=m;i++)
- {
- scanf("%d%d%d %c",&u,&v,&cost,&c);
- AddEdge(u,v,cost);
- }
- printf("%d\n",dist[BFS(BFS(u))]);
- }
- return 0;
- }