首页 > 代码库 > BZOJ 3363 POJ 1985 Cow Marathon 树的直径
BZOJ 3363 POJ 1985 Cow Marathon 树的直径
题目大意:给出一棵树。求两点间的最长距离。
思路:裸地树的直径。两次BFS,第一次随便找一个点宽搜。然后用上次宽搜时最远的点在宽搜。得到的最长距离就是树的直径。
CODE:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 80010 using namespace std; int points,edges; int head[MAX],total; int next[MAX],aim[MAX],length[MAX]; int f[MAX]; char s[10]; inline void Add(int x,int y,int len); inline void BFS(int start); int main() { cin >> points >> edges; for(int x,y,len,i = 1;i <= edges; ++i) { scanf("%d%d%d%s",&x,&y,&len,s); Add(x,y,len),Add(y,x,len); } BFS(1); int _max = 0; for(int i = 1;i <= points; ++i) if(f[i] > f[_max]) _max = i; BFS(_max); int ans = 0; for(int i = 1;i <= points; ++i) if(f[i] > ans) ans = f[i]; cout << ans << endl; return 0; } inline void Add(int x,int y,int len) { next[++total] = head[x]; aim[total] = y; length[total] = len; head[x] = total; } inline void BFS(int start) { static queue<int> q; while(!q.empty()) q.pop(); memset(f,0x3f,sizeof(f)); f[0] = f[start] = 0; q.push(start); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x];i;i = next[i]) if(f[aim[i]] > f[x] + length[i]) { f[aim[i]] = f[x] + length[i]; q.push(aim[i]); } } }
BZOJ 3363 POJ 1985 Cow Marathon 树的直径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。