Farthest Nodes in a Tree (求树的直径)
Description
Given a tree (a connected graph with no cycles), you have to find the farthest nodes in the tree. The edges of the tree are weighted and undirected. That means you have to find two nodes in the tree whose distance is maximum amongst all nodes.
Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with an integer n (2 ≤ n ≤ 30000) denoting the total number of nodes in the tree. The nodes are numbered from 0 to n-1. Each of the next n-1 lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000) denoting that node u and v are connected by an edge whose weight is w. You can assume that the input will form a valid tree.
Output
For each case, print the case number and the maximum distance.
Sample Input
2
4
0 1 20
1 2 30
2 3 50
5
0 2 20
2 1 10
0 3 29
0 4 50
Sample Output
Case 1: 100
Case 2: 80
#include<cstdio>
#include<string.h>
#include<algorithm>
#define M 30010
#include<queue>
using namespace std;
int a,b,c,head[M],ans,flag[M],sum[M],node,num,i,n;
/* head表示每个节点的头“指针”
num表示总边数
ans记录最后的结果
flag[]标记访问过的节点
sum[]表示以该节点结尾的最长路
*/ struct stu
{
int from,to,val,next;
}st[M*];
void add_edge(int u,int v,int w)
{
st[num].from=u;
st[num].to=v;
st[num].val=w;
st[num].next=head[u];
head[u]=num++;
}
void bfs(int fir)
{
int u;
queue<int> que;
memset(flag,,sizeof(flag));
memset(sum,,sizeof(sum));
flag[fir]=;
que.push(fir);
ans=;
while(!que.empty())
{
u=que.front();
que.pop();
for(i = head[u] ; i != - ; i = st[i].next)
{
if(!flag[st[i].to] && sum[st[i].to] < sum[u] + st[i].val)
{
sum[st[i].to]=sum[u]+st[i].val;
flag[st[i].to]=;
if(ans < sum[st[i].to])
{
ans=sum[st[i].to];
node=st[i].to; //记录以fir为起点的最长路的端点
}
que.push(st[i].to);
}
} }
}
int main()
{
int k=;
int t;
scanf("%d",&t);
while(t--)
{
num=;
memset(head,-,sizeof(head));
scanf("%d",&n);
for(i = ; i < n ; i++)
{
scanf("%d %d %d",&a,&b,&c);
add_edge(a,b,c);
add_edge(b,a,c);
}
bfs();
bfs(node);
printf("Case %d: %d\n",++k,ans);
}
}
最新文章
- CFBundleVersion与CFBundleShortVersionString,上架注意事项
- LR11启动卡修改
- haproxy 配置
- 20150813 Asp.net 关闭子窗体 刷新Tree控件
- ThinkPHP C+F方式
- C# 释放非托管资源
- 有关js的变量、作用域和内存问题
- 【转】PHP网站常见安全漏洞,及相应防范措施总结
- 动态类(Dynamic)应用
- css3动画实例测试
- 实验吧Web-天网管理系统
- CCNP第一课:默认路由(路由黑洞,路由终结)
- python之 文件读与写
- ORACLE 中NUMBER类型默认的精度和Scale问题
- easyui表格排序
- opencart3图片Google Merchant Center验证通过不了的解决方法
- ExtJs常用功能
- VSTO:使用C#开发Excel、Word【17】
- Kubernetes-1
- 反向代理/负载均衡/session/cookie