我的算法是每次找没有被入栈的ci最大的点,将他的没有入栈的父亲和父亲的父亲...依此入栈
然后从栈底开始求和,代码如下?这个贪心的方法不对?
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct pi
{
	int c,id,sd;
}p[1010],t[1010];

int f[1010],pt[1010];
bool v[1010];

int cmp (const void *a,const void *b)
{
	int d= (((struct pi*)a)->c - ((struct pi *)b)->c);
	if (d>0) return 1;
	else if (d<0) return -1;
	int e=((struct pi *)a)->sd - ((struct pi *)b)->sd;
	if (e>0) return 1;
	else if (e<0) return -1;
	else return 0;
}

int main ()
{
	int n,r,fa,sn,i,tmp,ts,cnt,cn,sum;
	while (scanf ("%d%d",&n,&r) && (n || r))
	{
		memset (p,0,sizeof (p));
		memset (v,0,sizeof (v));
		memset (f,0,sizeof (f));
		memset (pt,0,sizeof (pt));

		for (i=1;i<=n;i++)
		{
			scanf ("%d",&p[i].c);
			p[i].id=i;
		}
		for (i=1;i<n;i++)
		{
			scanf ("%d%d",&fa,&sn);
			f[sn]=fa;
		}
		for (i=1;i<=n;i++)
		{
			cnt=0;
			tmp=i;
			while (tmp) 
			{
				cnt++;
				tmp=f[tmp];
			}
			p[i].sd=cnt;
		}
		memcpy (t,p,sizeof (p));
		qsort (&p[1],n,sizeof (p[0]),cmp);	
		cn=0;
		for (i=n;i>=1;i--)
		{
			tmp=p[i].id;
			if (v[tmp]==0)
			{
				cnt=cn;
				while (tmp>0)
				{
					if (v[tmp]==0) 
					{
						cnt++;
						tmp=f[tmp];
					}
					else break;
				}
				cn=cnt;
				tmp=p[i].id;
				while (tmp>0)
				{
					if (v[tmp]==0)
					{
						pt[cnt]=tmp;
						cnt--;
						v[tmp]=1;
						tmp=f[tmp];
					}
					else break;
				}
			}
		}
		sum=0;
		for (i=1;i<=n;i++)
			sum+=i*t[pt[i]].c;
		printf ("%d\n",sum);
	}
	return 0;
}

• 问一下大家的做法中r这个变量有用吗?我的做法中这个东西没有用到... (0) washington 2005-08-20 00:26:38
  • 这个题我没做过， 不过我觉得一般情况下题目给的数据应该有用 (0) sunmoonstar_love 2005-08-20 00:33:23
    • 看大家的讨论似乎这个量没有什么用处 (0) Washington 2005-08-20 00:36:04
• Re:color a tree (why my mathod is wrong?) another one but still wa (1416) Washington 2005-08-20 01:38:53
  • Re:color a tree (why my mathod is wrong?) another one but still wa (177) cxf476 2006-04-02 19:33:02