| 比赛 | 
    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");
}