首页 > 代码库 > SDUT OJ 3045 迷之图论 (树的直径)
SDUT OJ 3045 迷之图论 (树的直径)
题目地址:SDUT OJ 3045
这题比赛的时候想的差不多。。但是总是觉得不对。。写了一次就没再写,然后删了。。当时没想到的是第二次求出来的就是最长链。。当时想到的两次bfs找最大值(这一种方法其实结果也对。。TAT。。),还有找到点后在回溯减去重点等等。。但总觉得好像都不太对。。。赛后才知道这题原来是树的直径。。。。。牡丹江区域现场赛的时候遇到过,不过赛后也没看。。。
找树的直径的方法其实就是先任取一点进行bfs,找到最远的一点,这时最远的一点肯定是最长链端点之一,然后再从这一最远点开始bfs,这时另一个端点就找到了,长度就是bfs的深度。
看的其他地方的证明如下:
关键在于证明第一次遍历的正确性,也就是对于任意点u,距离它最远的点v一定是最长路的一端。
如果u在最长路上,那么v一定是最长路的一端。可以用反证法:假设v不是最长路的一端,则存在另一点v’使得(u→v’)是最长路的一部分,于是len(u→v’) > len(u→v)。但这与条件“v是距u最远的点”矛盾。
如果u不在最长路上,则u到其距最远点v的路与最长路一定有一交点c,且(c→v)与最长路的后半段重合(why?),即v一定是最长路的一端。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; #define LL __int64 const int INF=0x3f3f3f3f; int head[110001], cnt, vis[110001], pos, d; struct node { int u, v, next; } edge[210001]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } struct node1 { int n, ans; }; void bfs(int source) { memset(vis,0,sizeof(vis)); vis[source]=1; node1 f1, f2; queue<node1>q; f1.n=source; f1.ans=0; q.push(f1); while(!q.empty()) { f1=q.front(); pos=f1.n; d=f1.ans; q.pop(); int u=f1.n; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(!vis[v]) { f2.n=v; f2.ans=f1.ans+1; vis[v]=1; q.push(f2); } } } } int main() { int n, i, j, u, v; while(scanf("%d",&n)!=EOF) { if(n==1) { printf("1\n"); continue ; } memset(head,-1,sizeof(head)); cnt=0; for(i=0; i<n-1; i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } bfs(1); bfs(pos); printf("%d\n",d+1); } return 0; }
SDUT OJ 3045 迷之图论 (树的直径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。