沒想到這個暴力題讓我郁悶了半小時，最后發(fā)現(xiàn)原來是回溯的問題?；竟Σ辉鷮嵃?。。。
#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)
這題是本次比賽最大的失誤，很多人直接搜的過了，不知道是不是因為數(shù)據(jù)的原因，
這也勢必導致很多人在比賽中非常的郁悶，在此也表示道歉，特別是對浙大的隊伍，
最后還有半個小時的時候看，前50多名只有浙大的兩個隊伍沒有過的，還好最后還是
都過了看來以后驗題的時候也還是要盡量考慮暴力暴力再暴力的方法啊。。。
校賽某題的續(xù)集，賽前和彩票哥說起這題的時候，在yy史哥他們隊會不會因為校賽沒
搞出F而對這個題留下陰影呢，還好這次他們成功避免了悲劇，而且是最早過的幾個
中，唯一的正解，其他都是搜過的。
這個題的模型，任意兩點之間有且只有一條有向邊，用彩票哥的話來說叫做競賽圖，
競賽圖必然存在一條哈密爾頓路，有一個很巧妙的構造方法。首先，只有兩個點的時
候，自然是存在哈密爾頓路的。假設K個點的競賽圖存在漢密爾頓路，V0->V1->…Vk
則考慮新加入節(jié)點Vk+1，如果有Vk+1->V0或者Vk->Vk+1，則自然可以在頭或者尾加入
延長路，否則的話，一定可以證明存在0<=i<k，使得同時存在Vi->Vk+1和Vk+1->Vi+1
也就是說可以在中間某個地方把Vk+1加進去延長漢密爾頓路。于是整個模擬過程通過
鏈表就可以很好的實現(xiàn)，根據(jù)彩票哥的解釋，還可以利用分治的思想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.