首页 > 代码库 > UVa 10308 Roads in the North 树的直径
UVa 10308 Roads in the North 树的直径
题目来源:UVa 10308 Roads in the North
题意:求距离最远的2点之间的距离
思路:裸的树的直径 或者树形DP
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn = 100010; struct node { int to, w; node(){} node(int to, int w): to(to), w(w) {} bool operator < (const node& rhs) const { return w < rhs.w; } }; vector <node> G[maxn]; int dis[maxn]; bool vis[maxn]; int path[maxn]; int p, leaf, n; void BFS(int s) { memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); memset(path, 0, sizeof(path)); queue <int> Q; Q.push(s); vis[s] = true; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = 0; i < G[u].size(); i++) { node x = G[u][i]; int v = x.to; if(vis[v]) continue; vis[v] = true; dis[v] = dis[u] + x.w; path[v] = u; //printf("%d\n", dis[v]); if(leaf < dis[v]) { p = v; leaf = dis[v]; } Q.push(v); } } } int main() { char str[100]; while(gets(str)) { for(int i = 1; i <= 10000; i++) G[i].clear(); if(strlen(str) == 0) { puts("0"); continue; } int u, v, w; sscanf(str, "%d %d %d", &u, &v, &w); G[u].push_back(node(v, w)); G[v].push_back(node(u, w)); while(gets(str) && strlen(str) > 0) { sscanf(str, "%d %d %d", &u, &v, &w); G[u].push_back(node(v, w)); G[v].push_back(node(u, w)); } leaf = 0; BFS(1); leaf = 0; BFS(p); printf("%d\n", leaf); } return 0; } /* 5 1 6 1 4 5 6 3 9 2 6 8 6 1 7 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。