> #include <stdio.h>
> #include <string.h>
> typedef struct arcNode
> {
> 	int son,dif;
> 	struct arcNode *next;
> }arcNode;
> typedef struct
> {
> 	char name[128];
> 	int age;
> 	struct arcNode *next;
> }Node;
> typedef struct List
> {
> 	char *name;
> 	struct List *next;
> }List;
> Node d[128];
> List a[128];
> bool flag[128];
> int pos,start;
> void init()
> {
> 	for(int i=0;i<128;i++)
> 	{
> 		d[i].next=NULL;
> 		a[i].name="";
> 		a[i].next=NULL;
> 	}
> }
> int locate(char *s)
> {
> 	int i;
> 	for(i=0;i<pos;i++)
> 		if(strcmp(s,d[i].name)==0)
> 			return i;
> 	strcpy(d[pos].name,s);
> 	if(strcmp(s,"Ted")==0)
> 	{
> 		d[pos].age=100;
> 		start=pos;
> 	}
> 	pos++;
> 	return pos-1;
> }
> //桶排+插入排序。
> void insert(int x)
> {
> 	int index=d[x].age;
> 	List *p=&a[index],*q,*ptr;
> 	while(p&&strcmp(p->name,d[x].name)<0)
> 	{
> 		q=p;
> 		p=p->next;
> 	}
> 	ptr=new List;
> 	ptr->name=d[x].name;
> 	ptr->next=q->next;
> 	q->next=ptr;
> }
> //从ted开始ＤＦＳ．
> void DFS(int x)
> {
> 	flag[x]=true;
> 	insert(x);　　　　　　　　//插入桶中。
> 	for(arcNode *p=d[x].next;p;p=p->next)
> 		if(!flag[p->son])
> 		{
> 			d[p->son].age=d[x].age-p->dif;
> 			DFS(p->son);
> 		}
> }
> int main()
> {
> 	int t,i,differ,n,c=0,px,py;
> 	arcNode *ptr;
> 	char fn[128],sn[128];
> 	scanf("%d",&t);
> 	while(t--)
> 	{
> 		scanf("%d",&n);
> 		init();
> 		for(pos=i=0;i<n;i++)
> 		{
> 			scanf("%s%s%d",fn,sn,&differ);
> 			px=locate(fn);
> 			py=locate(sn);
> 			ptr=new arcNode;
> 			ptr->son=py;
> 			ptr->dif=differ;
> 			ptr->next=d[px].next;
> 			d[px].next=ptr;
> 		}
> 		DFS(start);
> 		printf("DATASET %d\n",++c);
> 		for(i=99;i>0;i--)
> 		{
> 			List *pt=a[i].next;
> 			while(pt)
> 			{
> 				printf("%s %d\n",pt->name,i);
> 				pt=pt->next;
> 			}
> 		}
> 		memset(flag,false,sizeof(flag));
> 	}
> 	return 0;
> }

• Re:一直wa,测试了许多例子都没出错,晕,哪位大牛路过看下，谢啦! (45) try99 2007-05-29 08:13:15
  • 偶也是..bfs.被sort给整了 (55) crackerwang 2007-09-20 11:40:15
  • Re:一直wa,测试了许多例子都没出错,晕,哪位大牛路过看下，谢啦! (55) JLKJ_ZHUSHAN 2010-07-28 15:24:57