97全國資訊學科能力競賽 3. 找關鍵人物
作法 : 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
*/