ACM/ICPC 之 DFS求解欧拉回路+打表(POJ1392)

  本题可以通过全部n位二进制数作,而后可按照某点A的末位数与某点B的首位数相等来建立A->B有向边,以此构图,改有向图则是一个有向欧拉回路,以下我利用DFS暴力求解该欧拉回路得到的字典序最小的路径。

//求咬尾数,一个2^n位环形二进制数,该二进制的每n位连续二进制数都不同
//DFS求解欧拉回路
//Time:32ms Memory:1668K
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAX 16
#define MAXK (1<<15) int circle[MAX][MAXK];
bool v[MAXK];
int n; bool dfs(int rk, int x)
{
int t[2], mod = 1 << n;
if(rk == mod + n - 1) return true; //可生成所有n位二进制数
t[0] = (x << 1) & (mod - 1); //向后移动补0
t[1] = t[0] | 1; //向后移动补1
for(int i = 0; i < 2; i++)
{
if(!v[t[i]]){
v[t[i]] = true;
if(rk >= mod) //最后一位超过该咬尾数,可成环继续,否则回溯
{
if(circle[n][rk%mod] != (t[i] & 1))
return false;
}
else circle[n][rk] = i;
if(dfs(rk+1, t[i])) return true;
v[t[i]] = false;
}
}
return false;
} int main()
{
//freopen("in.txt","r",stdin); for(n = 1; n < MAX; n++)
{
memset(v,false,sizeof(v));
v[0] = true;
dfs(n,0);
}
int k;
while(scanf("%d%d", &n,&k), n)
{
int sum = 0, mod = 1 << n;
for(int i = 0; i < n; i++)
{
sum += circle[n][(i+k)%mod]*(1 << (n - i - 1));
}
printf("%d\n",sum);
} return 0;
}
上一篇:[ACM] poj 1064 Cable master (二进制搜索)


下一篇:MAC 上搭建lua环境