首页 > 其他 > 详细

哈密顿绕行世界问题---hdu2181(全排列问题)

时间:2016-03-14 16:22:24      阅读:159      评论:0      收藏:0      [点我收藏+]

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2181

 题意很容易理解,dfs就可以了

 

技术分享
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <map>
#include <vector>

using namespace std;

typedef long long LL;

#define met(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f
#define N 25

int G[N][N], A[N], vis[N], t;

void dfs(int s, int k)
{
    if(k == 21)
    {
        if( G[A[20]][A[1]] )
        {
            A[21] = A[1];

            printf("%d: ", t++);

            for(int i=1; i<=21; i++)
                printf(" %d", A[i]);

            printf("\n");
        }
        return;
    }
    for(int i=1; i<=20; i++)
    {
        if( G[s][i] && !vis[i])
        {
            A[k] = i;
            
            vis[i] = 1;
            
            dfs(i, k+1);
            
            vis[i] = 0;
        }
    }
}

int main()
{
    int a, b, c, m;

    met(G, 0);

    for(int i=1; i<=20; i++)
    {
        scanf("%d %d %d", &a, &b, &c);

        G[i][a] = G[i][b] = G[i][c] = 1;
    }

    while(scanf("%d", &m), m)
    {
        t = 1;

        met(vis, 0);

        met(A, 0);

        A[1] = m;

        vis[m] = 1;

        dfs(m, 2);
    }
    return 0;
}
View Code

 

哈密顿绕行世界问题---hdu2181(全排列问题)

原文:http://www.cnblogs.com/zhengguiping--9876/p/5276017.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!