排序-北大-1694

[china_sjc]

#include<iostream.h>
#include<stdlib.h>
typedef struct
{
int r; //所需的石子数
int son; //指向儿子节点的指针
}NODE; //节点类型
int sons[202]; //所有节点的儿子
NODE p[201];//保存节点
int comp(const void *e1,const void *e2)
{
return *(int *)e2 - *(int *)e1;
}
int done(int k)
{

if(p[k].r != -1)
return p[k].r; //若节点k已求得，直接返回
int u,v,j;
int a[200];
v = p[k].son;
u = sons[v++];
for(j=0;j<u;j++)
{
if(p[sons[j+v]].r==-1)
p[sons[j+v]].r = done(sons[j+v]);//求k的子节点sons[j+v]所需石子数
a[j] = p[sons[j+v]].r;
}
qsort(a,u,sizeof(int),comp);////对a[]快速排序
int max = 0;
for(j=0;j<u;j++)
if(max < a[j] + j)
max = a[j] + j; /// 取最大的a[j]+j
return max;
}
void main(void)
{

int t,n;
int i,j,k,m;
cin>>t;
while(t-- >0)
{
cin>>n;
int sn = 0;
for(i=0;i<n;i++)
{
cin>>k>>m;
if(m==0)
{
p[k].r = 1;
p[k].son = -1;
continue;
}
p[k].son = sn;p[k].r = -1;
sons[sn++] = m;
for(j=0;j<m;j++)
cin>>sons[j+sn]; // 读入节点k的所有子节点
sn += m;
}
j = done(1);//取根节点所需石子数
cout<<j<<endl;
}
}