树的直径

Farthest Nodes in a Tree

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 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

这个题刚开始一直不理解,可能是对树的的直径比较陌生吧,可后来看看了看学长给我板子。我去咋这么简单emmm,我真是个智障呀。只要从任意一个节点出发然后找到距离他最远的节点,然后再让这个最远的出发去找距离这个最远的,这两个节点的距离就是树的直径! 这就是一个简单的板子题

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> pa;

bool flag[100100];
int step[100100];
vector<pa>v[100100];
int a,b,c,sum;
int t,n;

int dfs(int x)
{
    sum=0;
    memset(flag,0,sizeof flag);
    memset(step,0,sizeof step);
    queue<int>q;
    q.push(x);
    flag[x]=1;
    int yy=0;
    while(!q.empty() )
    {
        int xx=q.front() ;
        q.pop() ;
        if(step[xx]>sum)
        {
            sum=step[xx];
            yy=xx;
        }
        pa p;
        for(int i=0;i<v[xx].size() ;i++)
        {
            p=v[xx][i];
            int y=p.first ;
            if(!flag[y])
            {
                flag[y]=1;
                step[y]=step[xx]+p.second;
                q.push(y);
            }
        }
    }
    return yy;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;

        for(int i=1;i<=t;i++)
        {
            cin>>n;
            for(int k=0;k<n;k++) 
                v[k].clear() ;
            for(int j=1;j<n;j++)
            {
                cin>>a>>b>>c;
                v[a].push_back(make_pair(b,c));//双向存储便于查找
                 v[b].push_back(make_pair(a,c));     
            }
            dfs(dfs(0));
            cout<<"Case "<<i<<": "<<sum<<endl;
        }

    return 0;
}

E-Computer

描述 一所学校不久前买了第一台电脑(所以这台电脑的ID是1)。近年来,学校购买了N-1新电脑。每台新电脑都连接到一台先前安装的电脑上。学校的管理人员担心网络运行缓慢,希望知道第i台计算机需要发送信号的最大距离si(即到最远计算机的电缆长度)。您需要提供此信息。

提示:示例输入与此图对应。从图中,你可以看到计算机4离1最远,所以s1=3。计算机4和5是距离2最远的,所以s2=2。计算机5是离3最远的,所以s3=3。我们也得到了s4=4,s5=4。

输入 输入文件包含多组测试样例。在每组样例中,第一行中都有自然数n(n<=10000),然后是(n-1)行,其中包含对计算机的描述。第i行包含两个自然数-第i计算机所连接的计算机和用于连接的电缆长度。电缆总长度不超过10^9。输入行中的数字用空格分隔。

输出 对于每组样例,输出n行。第i行第i台计算机的到其他计算机的最大长度Si(1<=i<=n)。

样例输入 5 1 1 2 1 3 1 1 1 样例输出 3 2 3 4 4 提示 示例输入与此图对应。从图中,你可以看到计算机4离1最远,所以s1=3。计算机4和5是距离2最远的,所以s2=2。计算机5是离3最远的,所以s3=3。我们也得到了s4=4,s5=4。

这个一看见就直接蒙圈了Woc这咋搞,想了好久还是csdn了,从一个点出发寻找到距离它最远的点,然后在从这个点出发寻找距离它最远的点中间记录每个节点的最远路程,这样算的的路径都是距离该节点的最远路径,然后再从距离这个点的最远的点在进行dfs还更新节点距离,那么最后的结果就是了

#include<iostream>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

typedef pair<int,int> pa;
int n,maxlen,s;
vector<pa>v[100100];
int dp[100100];

int dfs(int x,int y,int l)
{
    if(maxlen<=l)
    {
        maxlen=l;
        s=x;
    }
    pa p;
    for(int i=0;i<v[x].size() ;i++)
    {
        p=v[x][i];
        if(p.first ==y) continue;
        else
        {    
            dfs(p.first ,x,l+p.second);
            dp[p.first]=max(dp[p.first],l+p.second);
        }
    }
}

int main()
{
    while(cin>>n)
    {
        int x,y;
        memset(dp,0,sizeof dp);
        for(int i=0;i<=n;i++) v[i].clear() ;
        for(int  i=2;i<=n;i++)
        {
            cin>>x>>y;
            v[x].push_back(make_pair(i,y));
            v[i].push_back(make_pair(x,y));  
        }
        s=0;
        maxlen=0;
        maxlen=0;
        dfs(1,-1,0);
        dfs(s,-1,0);
        dfs(s,-1,0);
        for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
    }
    return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU-1811-Rank of Tetris

    #HDU-1811-Rank of Tetris HDU-1811-Rank of Tetris

    某些人
  • 背包九讲

    01背包九讲里面最简单的一种了,但是也是最重要的一种,其他的几种基本上都可以用01背包的解题思路来去解决,接下来结合例题来解决一下吧;

    某些人
  • D. Minimax Problem

    time limit per test:5 seconds memory limit per test:512 megabytes inputstandard ...

    某些人
  • Java工具集-支持各种类型快速排序工具

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • UVA 10600 ACM Contest and Blackout(次小生成树)

    题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=...

    Ch_Zaqdt
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • 初级程序员面试不靠谱指南(三)

    二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

    一心一怿
  • 复习C艹(更新中)

    之前在win7中运行c/c++下个vc就可以编译运行了,现在换了Mac,上网一看需要下个xcode,哎哟,好大啊,当时又没网,捉急,咦,mac的终端可以编译cp...

    仇诺伊
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear

扫码关注云+社区

领取腾讯云代金券