POJ 1655 - Balancing Act 树型DP

Program:

 #include<iostream>  
#include<stdio.h>  
#include<string.h>  
#include<set>  
#include<ctime>  
#include<algorithm>  
#include<queue>  
#include<cmath>  
#include<map>  
#define oo 1000000007  
#define ll long long  
#define pi acos(-1.0)  
#define MAXN 20005  
using namespace std; 
struct node 
{ 
      int x,y,next; 
}line[MAXN*2]; 
int _next[MAXN],n,AnsData,AnsNote; 
bool used[MAXN]; 
void addline(int x,int y,int m) 
{ 
      line[m].next=_next[x],_next[x]=m; 
      line[m].x=x,line[m].y=y; 
      return; 
} 
int dfs(int x) 
{ 
      int k,data=0,num=0,t; 
      k=_next[x]; 
      while (k) 
      { 
            if (!used[line[k].y]) 
            { 
                  used[line[k].y]=true; 
                  t=dfs(line[k].y); 
                  data=max(t,data); 
                  num+=t; 
                  used[line[k].y]=false; 
            } 
            k=line[k].next; 
      } 
      num++; 
      data=max(data,n-num); 
      if ((data<AnsData) || (data==AnsData && AnsNote>x)) 
         AnsNote=x,AnsData=data; 
      return num; 
} 
int main() 
{ 
      int T,i,num;  
      scanf("%d",&T); 
      while (T--) 
      { 
             scanf("%d",&n); 
             memset(_next,0,sizeof(_next)); 
             num=0; 
             for (i=1;i<n;i++) 
             { 
                   int x,y; 
                   scanf("%d%d",&x,&y); 
                   addline(x,y,++num); 
                   addline(y,x,++num); 
             } 
             memset(used,false,sizeof(used)); 
             used[1]=true,AnsData=oo; 
             dfs(1); 
             printf("%d %d\n",AnsNote,AnsData); 
      } 
      return 0; 
} 

补充：软件开发 , C++ ,

上一个：UVA 10394 Twin Primes
下一个：HDU1284钱币兑换问题( 母函数打表)