PAT1053部分错误，给组不能通过的数据就行，谢谢
本帖最后由 leizh007 于 2013-03-13 23:11:32 编辑 题目地址：http://pat.zju.edu.cn/contests/pat-a-practise/1053
思路就是从每个节点遍历到根，如果和等于S就保存，然后排序输出。
不知道这个题在卡什么数据？？？
帮忙给组不能过的数据我自己调调就行，谢谢啦。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct child
{
int num;
int w;
}child;
typedef struct node
{
int w;
int top;
child c[101];
}node;
node A[100];
int cmp(const void *a,const void *b)
{
child *aa=(child *)a;
child *bb=(child *)b;
return bb->w-aa->w;
}
int cmp1(const void *a,const void *b)
{
return strcmp((char *)b,(char *)a);
}
int Stack[100],top,sum,s;
char S[100][100];
int tops[100],nu;
void dfs(int k)
{
int i;
sum+=A[k].w;
Stack[top++]=A[k].w;
if(A[k].top==0)
{
if(sum==s&&top>1)//这个地方加上top>1，第二个测试点对，第四个测试点错；要是不加top>1第二个测试点错，第四个测试点对。不知道后台数据到底是要干嘛？？？
{
tops[nu]=top;
for(i=0;i<top;i++)
S[nu][i]=Stack[i];
S[nu][i]='\0';
nu++;
}
}
else
for(i=0;i<A[k].top;i++)
dfs(A[k].c[i].num);
sum-=A[k].w;
top--;
}
int main()
{
int n,m,i,num,j,x;
scanf("%d %d %d",&n,&m,&s);
for(i=0;i<100;i++)
{
A[i].top=0;
tops[i]=0;
}
for(i=0;i<n;i++)
scanf("%d",&A[i].w);
for(i=0;i<m;i++)
{
scanf("%d",&num);
scanf("%d",&A[num].top);
for(j=0;j<A[num].top;j++)
{
scanf("%d",&x);
A[num].c[j].num=x;
A[num].c[j].w=A[x].w;
}
qsort(A[num].c,A[num].top,sizeof(A[num].c[0]),cmp);
}
top=0;sum=0;nu=0;
for(i=0;i<n;i++)
dfs(i);
qsort(S,nu,sizeof(S[0]),cmp1);
for(i=0;i<nu;i++)
{
for(j=0;j<tops[i]-1;j++)
printf("%d ",S[i][j]);
printf("%d\n",S[i][j]);
}
return 0;
}
