树的直径

poj 1383题目链接 题意：一个迷宫图，求最远两点的距离是多少，保证每两个点都是联通的。 思路：树的直径。 代码实现 1#include <cstdio> 2#include <cstring> 3#include <iostream> 4#include <algorithm> 5#include <vector> 6#include <queue> 7#include <set> 8#include <map> 9#include <string> 10#include <cmath> 11#include <cstdlib> 12#include <ctime> 13#define fst first 14#define sec second 15#define lson l,m,rt<<1 16#define rson m+1,r,rt<<1|1 17#define ms(a,x) memset(a,x,sizeof(a)) 18typedef long long LL; 19#define pi pair < int ,int > 20#define MP make_pair 21using namespace std; 22const double eps = 1E-8; 23const int dx4[4]={1,0,0,-1}; 24const int dy4[4]={0,-1,1,0}; 25const int inf = 0x3f3f3f3f; 26const int N=1E3+7; 27char maze[N][N]; 28bool vis[N][N]; 29int ans; 30int n,m; 31struct Point 32{ 33 int x,y; 34 int d; 35 bool ok () 36 { 37 if (x<0||y<0||x>=n||y>=m) return false; 38 if (maze[x][y]=='#') return false; 39 if (vis[x][y]) return false; 40 return true; 41 } 42 void out() 43 { 44 cout<<"x:"<<x<<" y:"<<y<<endl; 45 } 46}S,lst; 47void bfs(Point S) 48{ 49 queue<Point>q; 50 S.d = 0; 51 q.push(S); 52 ms(vis,false); 53 vis[S.x][S.y] = true; 54 while (!q.empty()) 55 { 56 Point cur = q.front(); 57 q.pop(); 58 for ( int i = 0 ; i < 4 ; i++) 59 { 60 Point nxt; 61 nxt.x = cur.x + dx4[i]; 62 nxt.y = cur.y + dy4[i]; 63 nxt.d = cur.d + 1; 64 if (!nxt.ok()) continue; 65 q.push(nxt); 66 vis[nxt.x][nxt.y] = true; 67 if (ans<nxt.d) 68 { 69 ans = nxt. d; 70 lst = nxt; 71 } 72 } 73// cout<<"ans:"<<ans<<endl; 74 } 75} 76int main() 77{ 78 #ifndef ONLINE_JUDGE 79 freopen("code/in.txt","r",stdin); 80 #endif 81 int T; 82 cin>>T; 83 while(T--) 84 { 85 ms(vis,false); 86 scanf("%d%d",&m,&n); 87 for ( int i = 0; i < n ; i++) scanf("%s",maze[i]); 88 for ( int i = 0 ; i < n ; i++) 89 for ( int j = 0 ; j < m ; j++) 90 if (maze[i][j]=='.') 91 { 92 S.x = i ; 93 S.y = j ; 94 } 95 ans = 0; 96 bfs(S); 97 ans = 0 ; 98 bfs(lst); 99 printf("Maximum rope length is %d.\n",ans); 100 } 101 #ifndef ONLINE_JUDGE 102 fclose(stdin); 103 #endif 104 return 0; 105}

hdu 4123 题目链接 题意：一棵树，定义 d[i] 为点 i 到树上某点的最大距离。给出若干查询，每个查询一个 x，问最多能有多少点满足这些点中，最大的 d 与最小的 d 的差小于等于 x。要求这些点的编号必须是连续的。

题目链接 题意：一棵树。。然后初始两个推雪机在点s，问如何选择路径使得处理完所有边上的积雪所耗费的汽油最少（走过一条有雪的边和一条没雪的边耗费的汽油一样） 思路：很容易想到，我们应该尽可能不走已经被清理过雪了的边，因为这样很浪费。。。这样不难想到应该是和树的直径有关。但是初始的位置是给定的。。。怎么办？突然发现由于是给了两个推雪机。。所以其实相当于。。。只有一个推雪机&我们可以从任意位置开始推雪。。。第二个问题是。。。对于不在直径上的边。。我们怎么算cost？解决办法是读边的时候进行记录。。。然后求直径的时候记录路径。。。对于一条边。。。只要有一个点不在直径上。。。那么这条边的代价就是2倍。。。

hdu4607题目链接 题意：给出一棵树。。。边权都为1. m个查询。。每个查询给一个k，表示只访问k个点。。。问每次的最小路径和是多少。。。 思路：我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何（深度的意思是说，与和该点最近的直径上的点的距离），距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d，那么k<=d+1的时候，答案为k-1，否则答案为d+(k-d-1)*2。。。

poj 3310 题目链接 题意：给出一个无向图，问是否满足：连通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。连通的话任意起点开始跑一遍 dfs？开一个 bool 数组标记走过的点，最后扫一遍，看是否有点没走过。

hdu 4514 题意：给出一个无向图，问是否有环，有的话输出 YES。如果没有环的话，输出最长路径。 思路：无向图判环用并查集就好。关于最长路径这里，一开始以为就是树的直径。 但是需要注意的是，题目并没有保证图一定是联通的，所以 gg 了。

hdu 2196 题意：给出一棵树，求距离每个点的最远距离是多少。 思路：最远距离什么的，能想到树的直径，但是有什么关系呢？我们在求树的直径的时候，直径的两个端点是可以知道的。如果再从两个端点分别做两次 bfs，每个点取两个距离的较大值就是答案。。？

poj2631 题意：一棵树中求两个点的最远距离。。。 思路：就是求树的直径。。。裸体。。。。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月12日 星期二 13时03分39秒 4File Name :code/poj/2631.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4+7; 34int n,m; 35vector < pi> edge[N]; 36int lst; 37int ans; 38int d[N]; 39bool vis[N]; 40 41 42void bfs( int s) 43{ 44 ms(d,0x3f); 45 ms(vis,false); 46 queue<int>q; 47 q.push(s); 48 vis[s] = true; 49 d[s] = 0 ; 50 51 while (!q.empty()) 52 { 53 int u = q.front() ; q.pop(); 54 lst = u ; 55// cout<<"u:"<<u<<endl; 56 int siz = edge[u].size(); 57 58 for ( int i = 0 ; i < siz ; i++) 59 { 60 int v = edge[u][i].fst; 61 if (vis[v]) continue; 62 vis[v] = true; 63 d[v] = d[u] + edge[u][i].sec; 64 ans = max(d[v],ans); 65 q.push(v); 66 } 67 } 68 69 int mx = 0; 70 for ( int i = 1 ; i <= n ; i++) 71 { 72// cout<<"i:"<<i<<" d[i]:"<<d[i]<<endl; 73 if (d[i]>mx) 74 { 75 mx = d[i]; 76 lst = i ; 77 } 78 } 79 80} 81int main() 82{ 83 #ifndef ONLINE_JUDGE 84 freopen("code/in.txt","r",stdin); 85 #endif 86 87 int u,v,w; 88 m = 0; 89 n = 0; 90 while (scanf("%d%d%d",&u,&v,&w)!=EOF) 91 { 92 edge[u].push_back(make_pair(v,w)); 93 edge[v].push_back(make_pair(u,w)); 94 m++; 95 n = max(n,u); 96 n = max(n,v); 97 } 98 ans = inf; 99 bfs(1); 100 ans = 0; 101// cout<<"lst:"<<lst<<endl; 102 bfs(lst); 103 cout<<ans<<endl; 104 105 #ifndef ONLINE_JUDGE 106 fclose(stdin); 107 #endif 108 return 0; 109}

poj1985 题意：求树上两点的最长距离。。。也就是传说中的树的直径。。。 思路： 两遍BFS ：先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径； 原理： 设起点为u，第一次BFS找到的终点v一定是树的直径的一个端点 证明： 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾) 2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证)，那么交点到v 必然就是直径的后半段了 所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度