专栏首页Zaqdt_ACMHDU 2196 Computer(树的直径)

HDU 2196 Computer(树的直径)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196

       题意是n台电脑,n-1条边,输出第距离i台电脑最远的距离是多少。

       思路就是不管那一台电脑,距离它最远距离的一定是树的直径的两个端点的其中一个,所以我们只需要求出树的直径的两个端点,然后再求出这两个端点到每个点的距离就好了,然后输出的时候比较一下就可以了。


AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define maxn 20005
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
  int to,next,w;
}Edge[maxn];
int head[maxn],num;
int dist[maxn], pre[maxn];
bool vis[maxn];
int T,n,m;

void init(){
  for(int i=0;i<=n;i++){
    head[i] = -1;
  }
  num = 0;
}

void add(int u,int v,int w){
  Edge[num].to = v;
  Edge[num].w = w;
  Edge[num].next = head[u];
  head[u] = num ++;
}

void bfs(int x){
  queue<int> q;
  memset(dist,0,sizeof(dist));
  memset(vis,false,sizeof(vis));
  q.push(x);
  while(!q.empty()){
    int u = q.front();
    q.pop();
    vis[u] = true;
    for(int i=head[u];i!=-1;i=Edge[i].next){
      int to = Edge[i].to;
      if(vis[to] == false){
        vis[to] = true;
        dist[to] = dist[u] + Edge[i].w;
        q.push(to);
      }
    }
  }
}

int main()
{
  while(~scanf("%d",&n)){
    init();
    for(int i=2;i<=n;i++){
      int v, w;
      scanf("%d%d",&v,&w);
      add(i, v, w);
      add(v, i, w);
    }
    bfs(1);
    int Max = 0;
    int pos = 0;
    for(int i=1;i<=n;i++){
      if(Max < dist[i]){
        Max = dist[i];
        pos = i;
      }
    }
    bfs(pos);
    Max = 0;
    for(int i=1;i<=n;i++){
      if(Max < dist[i]){
        Max = dist[i];
        pos = i;
      }
      pre[i] = dist[i];
    }
    bfs(pos);
    for(int i=1;i<=n;i++){
      printf("%d\n", max(pre[i], dist[i]));
    }
  }
  return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • AIM Tech Round 5 B. Unnatural Conditions(思维)

    题目链接:http://codeforces.com/contest/1028/problem/B

    Ch_Zaqdt
  • 51nod 1649 齐头并进(Codeforces 601A The Two Routes) (最短路)

    题目链接(Codeforces):http://codeforces.com/problemset/problem/601/A

    Ch_Zaqdt
  • 最少联通代价(dfs+曼哈顿距离)

    现在要把这 2 个连通块连通, 求最少需要把几个’.’转变成’X’。上图的例子中, 最少只需要把 3个’.’转变成’X’。下图用’*’表示转化为’X’的格点...

    Ch_Zaqdt
  • 【计算机本科补全计划】CCF计算机职业资格认证 2016-09 试题详解

    正文之前 我要东山再起了!!没错CCF迫在眉睫(其实是我以为报名之后一个月才考,结果报名截止之后一周就考试!(╯‵□′)╯︵┻━┻!!!还能好好做朋友吗!!)所...

    用户1687088
  • ZR国庆Round2解题报告

    然后刚T3暴力,刚完还有2h左右。。然后,,这时候我zz的选择去打T2的暴力,然而T2暴力真的不是一般的难写。。

    attack
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • LeetCode31|打印从1到最大的n位数

    这道题算是api的使用方式了,数据的计算,其实自己也没有什么好说的了,但是由于文章的字数必需要达到300字,所有有些时候就只好在这里唠会嗑了,因为文章的原创对于...

    码农王同学
  • 【剑指Offer】51. 数组中的逆序对

    在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

    瑞新
  • 3555: [Ctsc2014]企鹅QQ

    Description PenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供...

    attack
  • 【CodeForces 504A】Misha and Forest

    有n个点,代号分别为0到n-1,然后第i个点有di个相连点,与i 相连的点的XOR sum 为si,求所有的边。

    饶文津

扫码关注云+社区

领取腾讯云代金券