哈密顿绕行世界问题
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1506 Accepted Submission(s): 957
Problem Description
一个规则的实心十二面体，它的 20个顶点标出世界著名的20个城市，你从一个城市出发经过每个城市刚好一次后回到出发的城市。
Input
前20行的第i行有3个数,表示与第i个城市相邻的3个城市.第20行以后每行有1个数m,m<=20,m>=1.m=0退出.
Output
输出从第m个城市出发经过每个城市1次又回到m的所有路线,如有多条路线,按字典序输出,每行1条路线.每行首先输出是第几条路线.然后个一个: 后列出经过的城市.参看Sample output
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 30;
int line[maxn][maxn];
int num;int vis[maxn];
int ans[maxn] ;
void dfs(int step,int st,int u)
{
if(step == 21 && u == st)
{
printf("%d: ",num++);
for(int i = 1 ;i <= 20 ;i++)
printf(" %d",ans[i]);
printf(" %d\n",st);
return ;
}
ans[step] = u;
for(int i = 1 ;i <= 20 ;i++)
{
if(line[u][i]&&!vis[i])
{
vis[i] = 1;
dfs(step+1,st,i);
vis[i] = 0;
}
}
}
int main()
{
int a,b,c;
int m = 1;
//freopen("in.txt","r",stdin);
memset(line,0,sizeof(line));
for(int i = 1;i <= 20 ;i++)
{
scanf("%d%d%d",&a,&b,&c);
line[a][i] = line[i][a] = 1;
line[b][i] = line[i][b] = 1;
line[c][i] = line[i][c] = 1;
}
while(scanf("%d",&m) && m)
{
num = 1;
memset(vis,0,sizeof(vis));
dfs(1 , m ,m);
}
return 0;
}
hdu 2181 dfs水题
原文：http://blog.csdn.net/cq_pf/article/details/44592851
