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