摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DFS+組合

利用DFS的特性,當退回來的時候紀錄該點下的所有節點數

因為圖是一棵樹 所以

要記錄一個點被經過幾次的話

假如 他四周分團 分別是 1 2 3 個節點數的話

那必定是C 3取2 乘積的總和

/*********************************************************/

#include<stdio.h>        
#include<stdlib.h>        
short map[20001][200]={0},maptop[20001]={0};        
int used[20001]={0},T[20001]={0};  
short branch[20001][200]={0},btop[20001];  
int n;     
void DFS (int now,int last)        
{        
   int a;  
   for(a=0;a<maptop[now];a++)  
      if(used[map[now][a]]==0)  
         {  
           used[map[now][a]]=1;  
           DFS(map[now][a],now);  
           used[map[now][a]]=0;  
         }  
   T[last]+=T[now];  
   branch[last][++btop[last]]=T[now];  
}  
int time(int t,int num)  
{  
   int n,m;  
   int p[250][250]={0};  
   for(n=0;n<=t;n++)  
      {  
         p[n][0]=1;  
         for(m=1;m<=n;m++)  
            p[n][m]=p[n-1][m]+p[n-1][m-1]*branch[num][n];  
      }  
      return p[t][2];  
}  
main()        
{        
   while(scanf("%d",&n)==1)        
       {        
          int a,b,c,x,y;  
          for(a=1;a<=n;a++) {T[a]=1;maptop[a]=0;btop[0];}  
          for(a=0;a<n-1;a++)        
             {        
                scanf("%d %d",&x,&y);        
                map[x][maptop[x]++]=y;        
                map[y][maptop[y]++]=x;        
             }  
          for(a=1;a<=n;a++)  
             if(maptop[a]==1)  
                {used[a]=1;DFS(a,0);used[a]=0;break;}  
          int MAXX=0,MAXA;  
          for(a=1;a<=n;a++)  
             {  
                   branch[a][++btop[a]]=n-T[a];  
                   int temp=time(btop[a],a);  
                   if(MAXX<temp) {MAXX=temp;MAXA=a;}   
             }  
             printf("%d %d\n",MAXA,MAXX);  
       }        
   return 0;        
}        
/*     
8     
1 3     
2 3     
3 4     
4 8     
4 5     
5 6     
5 7     
*/