没想到这个暴力题让我郁闷了半小时，最后发现原来是回溯的问题。基本功不扎实啊。。。
#include<iostream>
#include<cstring>
using namespace std;
int n;
int v[200];
int order[200];
struct node
{
int t;
node *next;
}edge[100000];
int cc;
node hash[2000];
void init(int n)
{
cc=0;
int i;
for(i=0;i<=n;i++)
{
hash[i].t=-1;
hash[i].next=NULL;
}
}
/**//*void floyd()
{
int i,j,k;
for(i=1;i<=n;i++)
mm[i][i]=1;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(mm[i][k]==1&&mm[k][j]==1)
mm[i][j]=1;
}
}
}
*/
node* newnode()
{
node *t=&edge[cc];
cc++;
return t;
}
void add(int a,int b)
{
node *p=newnode();
p->t=b;
p->next=hash[a].next;
hash[a].next=p;
}
/**//*
bool check(int x)
{
int i;
for(i=1;i<=n;i++)
{
if(i==x)
continue;
else if(v[i]==0&&mm[x][i]==0)
return false;
}
return true;
}
*/
int f=0;
void dfs(int i,int s)
{
if(f==1)
return ;
//if(!check(i))
// return ;
v[i]=1;
order[s]=i;
if(s==n){f=1;return;}
node *p=&hash[i];
for(p=p->next;p;p=p->next) if(!v[p->t])
{
dfs(p->t,s+1);
if(f==1)
return;
v[p->t]=0;
}
}
int main()
{
int t;
scanf("%d",&t);
int i,j;
while(t--)
{
f=0;
scanf("%d",&n);
init(n);
int a,b;
int edgen=n*(n-1)/2;
for(i=1;i<=edgen;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
}
//floyd();
for(i=1;i<=n;i++)
{
memset(v,0,sizeof(v));
dfs(i,1);
if(f==1)
break;
}
if(f==0)
puts("Impossible");
else
{
for(i=1;i<n;i++)
printf("%d ",order[i]);
printf("%d\n",order[n]);
}
}
return 0;
}K Strange Country II 中等 15.87% (67/422) / 21.72% (151/695)
这题是本次比赛最大的失误，很多人直接搜的过了，不知道是不是因为数据的原因，
这也势必导致很多人在比赛中非常的郁闷，在此也表示道歉，特别是对浙大的队伍，
最后还有半个小时的时候看，前50多名只有浙大的两个队伍没有过的，还好最后还是
都过了看来以后验题的时候也还是要尽量考虑暴力暴力再暴力的方法啊。。。
校赛某题的续集，赛前和彩票哥说起这题的时候，在yy史哥他们队会不会因为校赛没
搞出F而对这个题留下阴影呢，还好这次他们成功避免了悲剧，而且是最早过的几个
中，唯一的正解，其他都是搜过的。
这个题的模型，任意两点之间有且只有一条有向边，用彩票哥的话来说叫做竞赛图，
竞赛图必然存在一条哈密尔顿路，有一个很巧妙的构造方法。首先，只有两个点的时
候，自然是存在哈密尔顿路的。假设K个点的竞赛图存在汉密尔顿路，V0->V1->…Vk
则考虑新加入节点Vk+1，如果有Vk+1->V0或者Vk->Vk+1，则自然可以在头或者尾加入
延长路，否则的话，一定可以证明存在0<=i<k，使得同时存在Vi->Vk+1和Vk+1->Vi+1
也就是说可以在中间某个地方把Vk+1加进去延长汉密尔顿路。于是整个模拟过程通过
链表就可以很好的实现，根据彩票哥的解释，还可以利用分治的思想nlogn的搞定构造
过程，大家可以yy。
这个正确解法也值得研究下 ，原来这叫竞赛图。。。
#include<iostream>
using namespace std;
int mm[105][105];
struct node
{
int t;
node *next;
}pool[100000];
int cnt=0;
node *h,*r;
node *newnode()
{
node *t;
t=&pool[cnt++];
return t;
}
void add(node *h,int a)
{
node *p=newnode();
p->t=a;
p->next=h->next;
h->next=p;
}
void init()
{
cnt=0;
h=newnode();
h->next=NULL;
h->t=-1;
if(mm[1][2]==1)
{
add(h,2);
add(h,1);
r=h->next->next;
}
else
{
add(h,1);
add(h,2);
r=h->next->next;
}
}
int main()
{
int t,n;
scanf("%d",&t);
//int f;
while(t--)
{
//f=0;
memset(mm,0,sizeof(mm));
int i;
scanf("%d",&n);
if(n==1)
{printf("1\n");continue;}
for(i=1;i<=n*(n-1)/2;i++)
{ int a,b;scanf("%d%d",&a,&b);
mm[a][b]=1;
}
init();
for(i=3;i<=n;i++)
{
//f=1;
if(mm[i][h->next->t]==1)
{
add(h,i);
// f=0;
}
else if(mm[r->t][i]==1)
{
add(r,i);
r=r->next;
// f=0;
}
else
{
for(node *p=h->next;p!=r;p=p->next)
{
if(mm[p->t][i]==1&&mm[i][p->next->t]==1)
{
add(p,i);
//f=0;
break;}
}
}
// if(f==1)
// break;
}
//if(f==1)
// printf("Impossible\n");
//else
//{
for(node *p=h->next;p!=r;p=p->next)
printf("%d ",p->t);
printf("%d\n",r->t);
//}
}
return 0;
}
果然竞赛图没有impossible的情况，我把判断全部去掉后，100MS AC.