URAL 1056. Computer Net

红太狼 2021-12-23 19:11 182阅读 0赞

## 1056. Computer Net ##

Time limit: 2.0 second Memory limit: 64 MB

### Background ###

Computer net is created by consecutive computer plug-up to one that has already been connected to the net. Each new computer gets an ordinal number, but the protocol contains the number of its parent computer in the net. Thus, protocol consists of several numbers; the first of them is always 1, because the second computer can only be connected to the first one, the second number is 1 or 2 and so forth. The total quantity of numbers in the protocol is   *N* − 1 ( *N*  is a total number of computers). For instance, protocol 1, 1, 2, 2 corresponds to the following net:

The distance between the computers is the quantity of mutual connections (between each other) in chain. Thus, in example mentioned above the distance between computers \#4 and \#5 is 2, and between \#3 and \#5 is 3.

*Definition.*  Let the center of the net be the computer which has a minimal distance to the most remote computer. In the shown example computers \#1 and \#2 are the centers of the net.

### Problem ###

Your task is to find all the centers using the set protocol.

### Input ###

The first line of input contains an integer   *N*, the quantity of computers (2 ≤  *N* ≤ 10000). Successive   *N* − 1 lines contain protocol.

### Output ###

Output should contain ordinal numbers of the determined net centers in ascending order.

### Sample ###

<table style="border:1px solid #000000;border-collapse:collapse;"> 
 <tbody> 
  <tr> 
   <th style="border:1px solid #000000;color:#000000;vertical-align:top;">input</th> 
   <th style="border:1px solid #000000;color:#000000;vertical-align:top;">output</th> 
  </tr> 
  <tr> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>5
1
1
2
2
</pre> </td> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>1 2
</pre> </td> 
  </tr> 
 </tbody> 
</table>

**Problem Source: **Rybinsk State Avia Academy

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

一棵树，求最长路径的中点

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*求树的最长路径，
     2   两次dfs（），
     3   第一次求最大深度
     4   第二次反向求路径，
     5   求这条最长路径的中点值；
     6   偶取2个，奇取1个；
     7   注意要用链式前向星存储（数据量大），
     8 */
     9 #include<iostream>
    10 #include<string>
    11 #include<cstring>
    12 #include<cstdio>
    13 #include<cmath>
    14 #include<algorithm>
    15 using namespace std;
    16 struct  node
    17 {
    18     int  n,next;
    19 }e[20010];
    20 int n,m,i,j,k,top,maxdep;
    21 int ind;
    22 int head[10010];
    23 int check[10010];
    24 int pre[10010];
    25 void init()
    26  {
    27      cin>>n;
    28      top=0;
    29      for(i=1;i<=n;i++)
    30       {
    31           head[i]=-1;
    32           check[i]=0;
    33       }
    34      for(i=2;i<=n;i++)//链式前向星
    35       {
    36           cin>>k;
    37           e[top].n=i;
    38           e[top].next=head[k];
    39           head[k]=top++;
    40           e[top].n=k;
    41           e[top].next=head[i];
    42           head[i]=top++;
    43       }
    44  }
    45  void dfs(int v,int t)//dfs();
    46    {
    47        check[v]=1;
    48        if(maxdep<t)
    49         {
    50             maxdep=t;
    51             ind=v;
    52         }
    53         int q=head[v];
    54         while(q!=-1)
    55          {
    56              if(!check[e[q].n])
    57               {
    58                   pre[e[q].n]=v;
    59                   dfs(e[q].n,t+1);
    60               }
    61             q=e[q].next;
    62          }
    63 
    64    }
    65    int main()
    66    {
    67        init();
    68        maxdep=-1;
    69        dfs(1,1);//求深度
    70        for(i=1;i<=n;i++)
    71         {
    72             check[i]=0;
    73             pre[i]=-1;
    74         }
    75         maxdep=-1;
    76         dfs(ind,1);//记录路径
    77         i=ind;
    78         top=0;
    79         while(i!=-1)
    80          {
    81              check[top++]=i;
    82              i=pre[i];//求路径
    83          }
    84          if((top&1)==0)//判断输出
    85           cout<<check[(top>>1)-1]<<' '<<check[(top>>1)]<<endl;
    86          else
    87           cout<<check[top>>1]<<endl;
    88          return 0;
    89 
    90    }

坚持！！！！！！！

转载于:https://www.cnblogs.com/sdau--codeants/p/3307736.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/9ffba87f3d854cbca6d0411a6333ec4e.png