xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

int  N;
int  yes[ 1550 ],no[ 1550 ];
int  chd[ 3050 ],pre[ 3550 ],las[ 1550 ];
int  vis[ 1550 ];
inline 
int  min( int  x, int  y){
    
return  x > y ? y:x;
}
void  treedp( int  x){
    yes[x]
= 1 ; no[x] = 0 ;
    vis[x]
= 1 ;
    
while (las[x]){
        
int  y = chd[las[x]];
        
if ( ! vis[y]){
            treedp(y);
            yes[x]
+= min(yes[y],no[y]);
            no[x]
+= yes[y];
        }
        las[x]
= pre[las[x]];
    }
}
int  main()
{
    scanf(
" %d " , & N);
    
int  c = 0 ,x,y,k;
    memset(las,
0 , sizeof (las));
    
for ( int  i = 1 ;i <= N; ++ i){
        scanf(
" %d%d " , & x, & k);
        
for ( int  j = 1 ;j <= k; ++ j){
            scanf(
" %d " , & y);
            
++ c; pre[c] = las[x]; chd[c] = y; las[x] = c;
            
++ c; pre[c] = las[y]; chd[c] = x; las[y] = c;
        }
    }
    memset(vis,
0 , sizeof (vis));
    treedp(
0 );
    printf(
" %d\n " ,min(yes[ 0 ],no[ 0 ]));
    
return   0 ;
}





posted on 2009-05-30 15:01 xfstart07 阅读(158) 评论(0)  编辑 收藏 引用

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