dfs：哈密顿绕行世界问题（HDU-2181）

哈密顿绕行世界问题（HDU-2181）

题解：一个规则的实心十二面体，它的 20个顶点标出世界著名的20个城市，你从一个城市出发经过每个城市刚好一次后回到出发的城市。

裸DFS；

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
const int mod=142857;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
const int N=5e5+10;

int a[maxn][maxn];
int ans[maxn];
int vis[maxn];
int m,cnt;

void dfs(int city,int step)
{
    if(city==m&&step==20)
    {
        cout<<++cnt<<":  ";
        for(int i=0; i<20; i++)
         cout<<ans[i]<<" ";
        cout<<m<<endl;
        return ;
    }
    ans[step]=city;
    for(int i=1; i<=3; i++)
    {
        if(!vis[a[city][i]])
        {
            vis[a[city][i]]=1;
            dfs(a[city][i],step+1);
            vis[a[city][i]]=0;
        }
    }
}

int main()
{
    int x,y,z;
    for(int i=1; i<=20; i++)
    {
        cin>>x>>y>>z;
        a[i][1]=x;
        a[i][2]=y;
        a[i][3]=z;
        sort(a[i],a[i]+3);
    }
    while(cin>>m&&m)
    {
        memset(vis,0,sizeof(vis));
        memset(ans,0,sizeof(ans));
        dfs(m,0);
    }
    system("pause");
    return 0;
}