`

2181 哈密顿绕行世界问题

阅读更多
好吧,没什么难度的,只是要注意那个 ‘0’ 的判断我用了控制台函数……这个不会的可以去查资料,百度之,谷歌之……
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.

URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2181
Name  : 2181 哈密顿绕行世界问题

Date  :Friday,August 12,2011
Time Stage : 1 hours around

Result:
4400410	2011-08-12 21:04:56 Accepted 2181 0MS 192K 1475 B C++ pyy


Test Data:

Review:
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define infinity	0x7f7f7f7f
#define minus_inf	0x80808080

#define MAXSIZE 21

int way, m ;
int city[MAXSIZE][3], route[MAXSIZE], used[MAXSIZE] ;

void dfs (int c, int cnt)
{
	int i ;
	route[cnt] = c ;
	if (c == m && cnt == 20)
	{
		printf ("%d:  %d ", way++, m) ;
		for (i = 1 ; i < 20 ; ++i)
			printf ("%d ", route[i]) ;
		printf ("%d\n", route[i]) ;
	}
	for (i = 0 ; i < 3 ; ++i)
	{
		if (!used[city[c][i]])
		{
			used[city[c][i]] = 1 ;
			dfs (city[c][i], cnt + 1) ;
			used[city[c][i]] = 0 ;
		}
	}
}

int main ()
{
	char c ;
	int i ;
	while (1)
	{
		c = getc (stdin) ;	// 从输入流中提取一个字符
		if (c == '0')
			break ;
		ungetc (c, stdin) ; // 把这个字符还回去
		for (i = 1 ; i <= 20 ; ++i)
			scanf ("%d%d%d", &city[i][0], &city[i][1], &city[i][2]) ;
		scanf ("%d", &m) ;

		memset (used, 0, sizeof (used)) ;
		way = 1 ;
		for (i = 0 ; i < 3 ; ++i)
		{
			used[city[m][i]] = 1 ;
			dfs (city[m][i], 1) ;
			used[city[m][i]] = 0 ;
		}
		getchar () ; // 别忘了吃掉一个多余的回车键
	}
	return 0 ;
}


0
2
分享到:
评论

相关推荐

    哈密顿环问题

    哈工大算法实验三,搜索算法(哈密顿环问题)求解哈密顿环 1.实现基于树的深度优先搜索算法,求解哈密顿环问题 2.实现哈密顿环的爬山法 3.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析...

    哈密顿回路问题 算法设计

    哈密顿回路问题 算法设计与分析 回溯法

    自己做的哈密顿回路问题.docx

    自己做的哈密顿回路问题.docx

    MIPS汇编语言解决哈密顿回路问题

    MIPS汇编语言解决哈密顿回路问题。深度优先搜索,非递归方法。

    基于贪心算法的马踏棋盘哈密顿回路问题

    1. 通过贪心算法对可以回到起点的环游解——哈密顿回路 进行了优化。当棋盘规模小于12时,能够迅速给出任意一个节点的一条哈密顿解 2. 若不要求回到起点最大规模可达60 3. 可以自定义是否回到起点,棋盘规模以及是否...

    哈密顿圈问题是NP完全的

    【哈密顿圈问题】 对于一个有向图G=(V,E),如果G中的圈C恰好经过每一个顶点一次,则称圈C是一个哈密顿圈。即,哈密顿圈构成一条经过所有的顶点,没有重复的“路线”。如图6是一个含有哈密顿圈的图。 图6 一个含有...

    哈密顿图的判断(mips实现)

    哈密顿图判断 输入一个具有n个顶点的无向图G,判断G是否有哈密尔顿回路。(哈密顿回路问题,建议使用递归解决)

    哈密顿图判定问题的多项式时间算法_姜新文.pdf

    P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困 难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个...

    基于MATLAB的哈密顿回路算法-TSP模拟退火 程序源代码.rar

    基于MATLAB的哈密顿回路算法-TSP模拟退火 程序源代码.rar

    对于哈密顿问题的遗传算法求解

    代码里面有详细解释,包括独立函数,以及对函数的使用,有两个例子,可以鲜明得看出函数的调用过程。方便同学们日后使用。

    论文研究-哈密顿路径问题的一种基于有穷自动机的DNA算法.pdf

    提出了一种基于有穷自动机的解决哈密顿路径问题的DNA算法,将有穷自动机的状态用含有DNA限制性内切酶的识别位点的DNA双链分子来编码,通过限制性内切酶的生物化学反应来实现状态的转移。算法的创新之处在于用DNA计算...

    哈密顿图 数学建模

    哈密顿图 数学建模```````````````````

    对相对论世界线的哈密顿公式的隐藏约束

    我们讨论相对论点粒子的哈密顿公式化的示例,尽管它看起来很简单,但它至关重要,因为正如Hojman最近指出的那样,因为许多点粒子系统可以在高维Rindler背景下转换为这种形式 。 结果表明,该系统可以配备隐藏的局部...

    用贪心算法求解哈密顿回路

    该程序用C语言编写(在VC++环境下运行即可),使用贪心算法求得最短哈密顿回路的近似解,简单易懂。 该程序用C语言编写(在VC++环境下运行即可),使用贪心算法求得最短哈密顿回路的近似解,简单易懂。

    论文研究-无向哈密顿图的一个充分必要条件及计算公式.pdf

    哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一。1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果。根据...

    局部哈密顿量基态的聚类扩展

    在多体量子物理学中,一个中心问题是... 最后,我们用局部哈密顿量验证了在单一演化下集群扩展的局部性特征的持久性,并为不平衡问题提供了应用:简化的GGE均衡证明和工作统计的累积扩展。 相互作用成自由量子猝灭。

    最短哈密顿回路算法C语言实现

    最短哈密顿回路,在无向图中由一个顶点出发,不重复的遍历所有顶点,最后回到出发点,找到最短的回路,用C语言实现,

    哈密顿回路 回溯法——C++代码

    课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的

    模块化哈密顿量的引力对偶

    在这项工作中,我们研究了具有半经典引力对偶的量子场论状态中关于任意空间区域定义的模块化哈密顿量。 我们在引力对偶中找到了一些处方,用于计算模块化哈密顿量对其定义状态(包括其对偶度量)以及状态周围的小...

Global site tag (gtag.js) - Google Analytics