一上來這個專題就死磕了這道題一上午，然後發現
類似二分圖？2h 樣例都過不去
類似狀壓？1h 過樣例了，WA 0
類似暴搜？10min AC
然而正解是歐拉回路
歐拉回路：
如果圖G中的一個路徑包括每個邊恰好一次，則該路徑稱爲歐拉路徑(Euler path)。如果一個迴路是歐拉路徑，則稱爲歐拉回路(Euler circuit)。具有歐拉回路的圖稱爲歐拉圖
判斷條件：
以下判斷基於此圖的基圖連通。無向圖存在歐拉回路的充要條件一個無向圖存在歐拉回路，當且僅當該圖所有頂點度數都爲偶數,且該圖是連通圖。有向圖存在歐拉回路的充要條件一個有向圖存在歐拉回路，所有頂點的入度等於出度且該圖是連通圖。
前k個一定是0，確定好初態後，每次轉移只會出現兩種情況：0或1
因此dfs即可
注意在末態判斷是要和初態完美契合
Code
#include<cstdio> #include<vector> int ak,k,a[5000],ans[5000],num,rnum,full[15],pow[15],q[5000]; void bfs(int la,int tot){ if(ak)return; if(tot==pow[k]){ if(ak)return; bool ok=1; //for(int i=1;i<=num;++i)printf("%d",ans[i]);puts(""); for(int i=1;i<=k-1;++i){ int up=((la<<i)&full[k]); if(a[up]){ok=0;break;} else q[++q[0]]=up,a[up]=1; } for(int i=1;i<=q[0];++i)a[q[i]]=0;q[0]=0; if(!ok)return; while(num)if(!ans[num])num--,rnum++;else break; for(int i=1;i<=rnum;++i)putchar('0'); for(int i=1;i<=num;++i)printf("%d",ans[i]);puts(""); ak=1; } la<<=1; if(!a[la]){ a[la]=1; ans[++num]=0; bfs(la&full[k-1],tot+1); a[la]=0; --num; } if(!a[la|1]){ a[la|1]=1; ans[++num]=1; bfs((la|1)&full[k-1],tot+1); a[la|1]=0; --num; } } int main(){ scanf("%d",&k); for(int i=0;i<=k;++i)full[i]=(1<<i)-1; for(int i=0;i<=k;++i)pow[i]=(1<<i); rnum=k; printf("%d ",pow[k]); a[0]=1;bfs(0,k); return 0; }