posts - 64, comments - 4, trackbacks - 0, articles - 0

hdu_3534 Tree

Posted on 2010-08-15 20:42 acronix 阅读(344) 评论(0)  编辑 收藏 引用 所属分类: hzshuai解题报告

题意:给你一棵树,求最长的路程及其数目。 
          
分析: 这道题做的我好辛苦啊,说是树形dp,我的理解此题其实是个树形递推(自顶向下使用递归实现自底向上的递推),唯一的记忆话就是标记访问过的节点,防止倒退。
        理解了这个,还有一个难点,就是计数的问题:当有过某个节点有多个最大值时的计数;当子树有相同最大值的计数的补充。
        总之,trick多多。还有本题可由任一节点开始递归,并不影响树的性质,倒是要注意第二种计数情况!!

#include <cstdio>
#include <
stdlib.h>

const
 int MAX =
 10010;

struct Point{
       int id,len;
       
struct
 Point *next;
} p[
2*
MAX],*head[MAX]; 

struct Recd{
       
bool flag;
//标记 
       
int max,num; 
//当前节点以下的所有最大值及数目 
       
int max_rout;
//以此节点为端点的最大值 
       
int max_num; 
//以此节点为端点的最大值的数目 
} a[MAX]; 
//记录各顶点的状态 

int n,x,y,v,cnt;

inline 
void addedge(int x,int y,int v)//用邻接表把各节点串起来 
{
       cnt 
++;
       p[cnt].id 
= y;
       p[cnt].len 
= v;
       p[cnt].next = head[x];
       head[x] 
=
 &p[cnt];
}

void
 dp(int root)
{
     a[root].flag 
=
 true;
     
struct Point *
q = head[root];
     
     
int m[2= {0
,0};
     
int m_cnt[2= {1
,1};
     
bool mark =
 false;
     
int son_max = -1 , son_num =
 0;
     
int tnum[2= {0
,0};
     
     while (q)
     {
           
if (a[q->id].flag == true)
//已访问过 
           {
              q 
=
 q->next;
              
continue;
           }
           dp(q->id);
           x 
= a[q->id].max_rout +
 q->len;
           y 
=
 a[q->id].max_num;
           
if (x >
 m[0])
           {
                 mark 
=
 false;
                 m[
1=
 m[0];
                 m_cnt[
1=
 m_cnt[0];
                 m[
0
] = x;
                 m_cnt[
0
] = y;
                 tnum[
0= 0
//pay attention 
           }
           
else if (x ==
 m[0])
                {
                      mark 
=
 true;
                      tnum[
0+= m_cnt[0
]*y;
                      m_cnt[
0
] += y;
                }
                
else if (x >
 m[1])
                     {
                           m[
1
] = x;
                           m_cnt[
1
] = y;
                     }
                     
else if(x ==
 m[1])
                           {
                               m_cnt[
1
] += y;
                           }
                 
           
if (son_max <
 a[q->id].max)
           {
              son_max 
=
 a[q->id].max;
              son_num 
=
 a[q->id].num;
           }
           
else if (son_max ==
 a[q->id].max)
                   son_num 
+=
 a[q->id].num;
           q 
=
 q->next;
     }
     
int temp ,sum;
     if (mark)
     {
              sum 
=
 tnum[0];
              temp 
= 2*
m[0];
     }
     else {
          temp 
= m[0+
 m[1];
          sum 
= m_cnt[0*
 m_cnt[1];
          }
     
     
if
 (temp < son_max)
     {
        temp 
= son_max;
        sum = son_num;
     }
     
else if (temp == son_max)
//pay attention
          {
                   sum += son_num;
          }
     
     a[root].max_rout 
=
 m[0];
     a[root].max_num 
=
 m_cnt[0];
     a[root].max 
= temp;
     a[root].num 
= sum;
}

int main()
{
    
while (scanf("%d",&
n) != EOF)
    {
          
for (int i = 1; i <=
 n; i++)
          {
              a[i].flag 
=
 false;
              head[i] = NULL;
          }
          cnt 
=
 0;
          
for (int i = 1; i <
 n; i++)
          {
              scanf(
"%d %d %d",&x,&
y,&v);
              addedge(x,y,v);
              addedge(y,x,v);
          }
        
          dp(1);
         printf(
"%d %d\n",a[1
].max,a[1].num);
    }
    
return
 0;

 


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