我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

URAL——1056——(树中心--BFS)

Posted on 2008-08-21 20:33 Hero 阅读(285) 评论(0)  编辑 收藏 引用 所属分类: 代码如诗--ACM
  1 //    1056    C++    Accepted    0.031    1 045 KB
  2 
  3 //twice BFS 第一次找离节点1最远的点K,再找离K最远的点X,
  4 //K--X就是最长链,链上的中点就是中心 O(n)
  5 
  6 #include <stdio.h>
  7 #include <stdlib.h>
  8 #include <string.h>
  9 
 10 const int size = 10010 ;
 11 struct NODE
 12 {
 13     int en ;
 14     struct NODE * next ;
 15     NODE() { next = NULL ; }
 16 };
 17 struct NODE nhead[size] ;
 18 
 19 struct QUEUE
 20 {
 21     int val ;
 22     int level ;
 23 };
 24 struct QUEUE que[size] ;
 25 int head, tail ;
 26 
 27 int line[size] ;
 28 int flag[size] ;
 29 
 30 int father[size] ;
 31 
 32 int inn ;
 33  
 34 int fmin( int a, int b )
 35 {
 36     return a < b ? a : b ;
 37 }
 38 
 39 int fmax( int a, int b )
 40 {
 41     return a > b ? a : b ;
 42 }
 43 
 44 void input()
 45 {
 46     memset( father, -1sizeof(father) ) ;
 47 
 48     int en ;
 49     forint i=2; i<=inn; i++ ) 
 50     {
 51         scanf( "%d"&en ) ; father[i] = en ;
 52         struct NODE *temp1 = (struct NODE *)malloc( sizeof(NODE) ) ;
 53         temp1->en = en ;
 54         temp1->next = nhead[i].next ; nhead[i].next = temp1 ;
 55         struct NODE *temp2 = (struct NODE *)malloc( sizeof(NODE) ) ;
 56         temp2->en = i ;
 57         temp2->next = nhead[en].next ; nhead[en].next = temp2 ;
 58     }//建图
 59 }
 60 
 61 void BFS( int sn )
 62 {
 63     memset( flag, 0sizeof(flag) ) ;
 64     que[tail].val = sn ; que[tail++].level = 1 ; flag[sn] = 1 ;
 65 
 66     int curn ; struct NODE *p ;
 67     while( head < tail )
 68     {
 69         curn = que[head].val ;
 70         p = nhead[curn].next ;
 71         while( NULL != p )
 72         {
 73             if0 == flag[p->en] ) 
 74             {
 75                 flag[p->en] = 1 ; 
 76                 que[tail].val = p->en ;
 77                 que[tail++].level = que[head].level + 1 ;
 78             }
 79             p = p->next ;
 80         }
 81         head++ ;//容易忘记
 82     }
 83 }
 84 
 85 void process()
 86 {
 87     head = tail = 0 ; BFS( 1 ) ;
 88 
 89     int leaf = que[tail-1].val ;
 90 
 91     head = tail = 0 ; BFS( leaf ) ;
 92 }
 93 
 94 void output()
 95 {//寻找最长链
 96         
 97     line[0= 0 ; int p = tail-1 ;
 98 
 99     int maxlen = que[tail-1].level ; line[maxlen] = que[tail-1].val ;
100     forint i=maxlen-1; i>=1; i-- )
101     {
102         while( que[p].level > i && p>=0 ) p-- ;
103 
104         while( father[que[p].val]!=line[i+1]&&father[line[i+1]]!=que[p].val && p>=0 ) p-- ;
105         line[i] = que[p].val ;
106     }
107 
108     int x = (maxlen+1)/2 ;
109     if1 == (maxlen&1) )
110     {
111         printf( "%d\n", line[x] ) ;
112     }
113     else
114     {
115         printf( "%d %d\n", fmin( line[x], line[x+1] ), fmax( line[x], line[x+1]) ) ;
116     }
117 }
118 
119 int main()
120 {
121     while( scanf( "%d"&inn ) != EOF )
122     {
123         input() ;
124 
125         process() ;
126 
127         output() ;
128     }
129 
130     return 0 ;
131 }

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理