比赛 20120224 评测结果 AAAAAAAAAA
题目名称 课程安排问题 最终得分 100
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-02-24 19:59:54
显示代码纯文本
#include <cstdio>

#define I_F "curriculum.in"
#define O_F "curriculum.out"

const short Maxn=100+1;

struct heap
{
	short m,l;
}s[Maxn];
short n;
bool map[Maxn][Maxn]={{false}};
bool flag=true;
short ans[Maxn];

inline bool Compare(const heap&, const heap&);
template <typename Any>
inline void Swap(Any&, Any&);
void Fixup(heap*, const short);
void Input();
void Fixdown(heap*, const short, const short);
void Search();
void Output();

int main()
{
	Input();
	Search();
	Output();
	return 0;
}

inline bool Compare(const heap &a, const heap &b)
{
	return (a.m<b.m || (a.m==b.m && a.l<b.l));
}

template <typename Any>
inline void Swap(Any &a, Any &b)
{
	Any t=a;
	a=b;
	b=t;
}

void Fixup(heap *s, const short x)
{
	for (short j=x; j>1 && Compare(s[j],s[j/2]); j/=2)
		Swap(s[j],s[j/2]);
}

void Input()
{
	short t;
	freopen(I_F,"r",stdin);
	scanf("%hd",&n);
	for (short i=1; i<=n; i++)
	{
		scanf("%hd",&s[i].m);
		for (short j=0; j<s[i].m; j++)
		{
			scanf("%hd",&t);
			map[t][i]=true;
		}
		s[i].l=i;
		Fixup(s,i);
	}
}

void Fixdown(heap *s, const short x,const short n)
{
	for (short j=x; ;)
		if (j*2>n)
			break;
		else
			if (j*2==n)
				if (Compare(s[j*2],s[j]))
				{
					Swap(s[j*2],s[j]);
					j*=2;
				}
				else
					break;
			else
				if (Compare(s[j*2],s[j*2+1]))
					if (Compare(s[j*2],s[j]))
					{
						Swap(s[j*2],s[j]);
						j*=2;
					}
					else
						break;
				else
					if (Compare(s[j*2+1],s[j]))
					{
						Swap(s[j*2+1],s[j]);
						j=j*2+1;
					}
					else
						break;
}

void Search()
{
	for (short i=0; i<n && flag; i++)
		if (s[1].m==0)
		{
			ans[i]=s[1].l;
			Swap(s[1],s[n-i]);
			Fixdown(s,1,n-i-1);
			
			for (short j=1; j<n-i; j++)
				if (map[s[n-i].l][s[j].l])
				{
					s[j].m--;
					Fixup(s,j);
				}
		}
		else
			flag=false;
}

void Output()
{
	freopen(O_F,"w",stdout);
	if (flag)
	{
		for (short i=0; i<n; printf("%hd ",ans[i++]));
		printf("\n");
	}
	else
		printf("no\n");
}