本文主要是介绍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
*/
这篇关于UVa 10308 Roads in the North 树的直径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!