现在经常发现原来做过的一些OJ的月赛题，与某些经典题有着很深的渊源...

有向图中，若对于任意点对i和j都有边（i,j）或边（j,i），则该有向图为竞赛图。而竞赛图的哈密顿路一定存在，因此[TOJ]1151最少的重启次数一定是1，[ZOJ]3332中没有impossible的情况。

思路是：任取一点作起点，然后逐个添加其他点。如果要把点x添加到已经连好的部分路径中,那么：

1.对于路径的第一个点a，若有边x->a,就把x加在路径首，如果没有，

2.对于路径的最后一个点b，若有边b->x，就把x加在路径末尾，如果没有

3.在路径a₁
,a₂
...a_k
中必能找到一个位置m，同时存在边a_m
->x和x->a_m+1
，插入之！

虽然我的代码效率不高（1151有两个0.00s的!），好歹也是第一次自己写的链表~

我先写的是[ZOJ]3332

#include<stdio.h><br /> #include<string.h><br /> #include<iostream><br /> #include<algorithm><br /> using namespace std;<br /> struct node{<br /> int no;<br /> node *next;<br /> }*first,*list,*newnode;<br /> int main(){<br /> //freopen("*.in","r",stdin);<br /> //freopen("*.out","w",stdout);<br /> int t,n,a,b,temp,i,j;<br /> bool f[101][101],flag;<br /> scanf("%d",&t);<br /> while(t--){<br /> scanf("%d",&n);<br /> if(n==1) {printf("1/n");continue;}<br /> memset(f,0,sizeof(f));<br /> temp=n*(n-1)/2;<br /> while(temp--){<br /> scanf("%d%d",&a,&b);<br /> f[a][b]=1;<br /> }<br /> /*<br /> printf(" ");<br /> for(i=1;i<=n;i++) printf(" %d",i);<br /> printf("/n");<br /> for(i=1;i<=n;i++){<br /> printf("%d",i);<br /> for(j=1;j<=n;j++) printf(" %d",f[i][j]);<br /> printf("/n");<br /> }<br /> */<br /> first=new node;<br /> first->next=NULL;<br /> first->no=1;<br /> for(i=2;i<=n;i++){<br /> /*<br /> list=first;<br /> printf("init list = ");<br /> while(list->next!=NULL){<br /> printf("%d ",list->no);<br /> list=list->next;<br /> }<br /> printf("%d/n",list->no);<br /> */<br /> flag=1;<br /> newnode=new node;<br /> newnode->no=i;<br /> if(f[i][first->no]){<br /> //printf("f[%d][%d]=%d/n",i,first->no,f[i][first->no]);<br /> newnode->next=first;<br /> first=newnode;<br /> flag=0;<br /> }<br /> /*<br /> list=first;<br /> printf("init2 list = ");<br /> while(list->next!=NULL){<br /> printf("%d ",list->no);<br /> list=list->next;<br /> }<br /> printf("%d/n",list->no);<br /> */<br /> if(flag){<br /> /*<br /> list=first;<br /> printf("list = ");<br /> while(list->next!=NULL){<br /> printf("%d ",list->no);<br /> list=list->next;<br /> }<br /> printf("%d/n",list->no);<br /> */<br /> list=first;<br /> while(list->next!=NULL&&flag){<br /> //printf("while list->no=%d/n",list->no);<br /> if(f[list->no][i]&&f[i][list->next->no]){<br /> newnode->next=list->next;<br /> list->next=newnode;<br /> flag=0;<br /> }<br /> list=list->next;<br /> }<br /> //printf("list->no=%d/n",list->no);<br /> if(flag&&f[list->no][i]) {<br /> //printf("ii=%d/n",i);<br /> newnode->next=NULL;<br /> list->next=newnode;<br /> }<br /> }<br /> //printf("i=%d/n",i);<br /> }<br /> while(first->next!=NULL){<br /> printf("%d ",first->no);<br /> first=first->next;<br /> }<br /> printf("%d/n",first->no);<br /> }<br /> //system("pause");<br /> return 0;<br /> }<br />
 

发现[TOJ]1151与其类似后，果断修改！

Show Code - Run ID 929267

Submit Time: 
2010-07-13 20:51:53     Language: 
GNU C++     Result: 
Accepted
    Pid: 
1151

     Time: 
0.61 sec.     Memory: 
2184 K.     Code Length: 
1.4 K.

#include<stdio.h><br /> #include<string.h><br /> #include<iostream><br /> #include<algorithm><br /> using namespace std;<br /> struct node{<br /> int no;<br /> node *next;<br /> }*first,*list,*newnode;<br /> bool f[1001][1001];<br /> int main(){<br /> int t,n,a,b,temp,i,j;<br /> bool flag;</p> <p> while(scanf("%d",&n)!=EOF){<br /> memset(f,0,sizeof(f));<br /> for(i=0;i<n;i++){<br /> for(j=0;j<n;j++){<br /> scanf("%d",&t);<br /> if(t) f[i+1][j+1]=1;<br /> }<br /> }<br /> printf("1/n%d/n",n);<br /> if(n==1) {printf("1/n");continue;}<br /> first=new node;<br /> first->next=NULL;<br /> first->no=1;<br /> for(i=2;i<=n;i++){<br /> flag=1;<br /> newnode=new node;<br /> newnode->no=i;<br /> if(f[i][first->no]){<br /> newnode->next=first;<br /> first=newnode;<br /> flag=0;<br /> }<br /> if(flag){<br /> list=first;<br /> while(list->next!=NULL&&flag){<br /> if(f[list->no][i]&&f[i][list->next->no]){<br /> newnode->next=list->next;<br /> list->next=newnode;<br /> flag=0;<br /> }<br /> list=list->next;<br /> }<br /> if(flag&&f[list->no][i]) {<br /> newnode->next=NULL;<br /> list->next=newnode;<br /> }<br /> }<br /> }<br /> while(first->next!=NULL){<br /> printf("%d ",first->no);<br /> first=first->next;<br /> }<br /> printf("%d/n",first->no);<br /> }<br /> //system("pause");<br /> return 0;<br /> }<br />