HDU 4337 King Arthur's Knights 它输出一个哈密顿电路

HDU 4337 King Arthur's Knights 它输出一个哈密顿电路

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

n积分m文章无向边

它输出一个哈密顿电路

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 155;

int n, m;
bool mp[N][N];

int S, T, top, Stack[N];
bool vis[N];
void _reverse(int l,int r) {
	while (l<r)
		swap(Stack[l++],Stack[r--]);
}
void expand() {
	while(1) {
		bool flag = 0;
		for (int i=1; i<=n && false == flag; i++)
			if (!vis[i] && mp[T][i])
			{
				Stack[top++]=i;
				T=i;
				flag = vis[i] = 1;
			}
		if (!flag) return;
	}
}
void hamiltun(int Start){
	memset(vis, 0, sizeof vis);

	S = Start;
	for(T=2; T<=n; T++) //随意找两个相邻的节点S和T
		if (mp[S][T]) break; 
	top = 0;
	Stack[top++]=S;
	Stack[top++]=T;
	vis[S] = vis[T] = true;
	while (1)
	{
		expand(); //在它们基础上扩展出一条尽量长的没有反复节点的路径:步骤1
		_reverse(0,top-1);
		swap(S,T);
		expand(); //在它们基础上扩展出一条尽量长的没有反复节点的路径
		int mid=0;
		if (!mp[S][T]) //若S与T不相邻,能够构造出一个回路使新的S和T相邻
		{
			//设路径S→T上有k+2个节点,依次为S,v1,v2…… vk和T.
			//能够证明存在节点vi,i∈[1,k),满足vi与T相邻,且vi+1与S相邻
			for (int i=1; i<top-2; i++)
				if (mp[Stack[i]][T] && mp[Stack[i+1]][S])
				{
					mid=i+1; break;
				}
			//把原路径变成S→vi→T→vi+1→S,即形成了一个回路
			_reverse(mid,top-1);
			T=Stack[top-1];
		}
		if (top==n) break;
		//如今我们有了一个没有反复节点的回路.假设它的长度为N,则汉密尔顿回路就找到了
		//否则,因为整个图是连通的,所以在该回路上,一定存在一点与回路以外的点相邻
		//那么从该点处把回路断开,就变回了一条路径,再依照步骤1的方法尽量扩展路径
		for (int i = 1, j; i <= n; i++)
			if (!vis[i])
			{
				for (j=1; j<top-1; j++)
					if (mp[Stack[j]][i]) break;
				if (mp[Stack[j]][i])
				{
					T=i; mid=j;
					break;
				}
			}
		S=Stack[mid-1];
		_reverse(0,mid-1);
		_reverse(mid,top-1);
		Stack[top++]=T;
		vis[T]=true;
	}
}

int main() {
	while (cin>>n>>m) {
		memset(mp, 0, sizeof mp);
		for (int i = 1, u, v; i <= m; i++) {
			scanf("%d %d",&u, &v);
			mp[u][v] = mp[v][u] = 1;
		}
		hamiltun(1);
		for (int i = 0; i < top; i++)
			printf("%d%c", Stack[i], i==top-1?'\n':' ');
	}
	return 0;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116761.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • MJKDZ PS2手柄控制OskarBot小车(一):Arduino串口发送数据

    MJKDZ PS2手柄控制OskarBot小车(一):Arduino串口发送数据MJKDZPS2手柄控制OskarBot小车(一):Arduino串口发送数据【目录】    -1、无线通信模块设置        -1.1设置参数        -1.2调试步骤    -2、按键与通信格式        -2.1PS2按键定义        -2.2发送数据格式    -3、源代码        -3.1串口手…

  • mysql utf8占几个字节_utf-8的中文是一个字符占几个字节

    mysql utf8占几个字节_utf-8的中文是一个字符占几个字节英文字母和中文汉字在不同字符集编码下的字节数英文字母:·字节数:1;编码:GB2312字节数:1;编码:GBK字节数:1;编码:GB18030字节数:1;编码:ISO-8859-1字节数:1;编码:UTF-8字节数:4;编码:UTF-16字节数:2;编码:UTF-16BE字节数:2;编码:UTF-16LE中文汉字:字节数:2;编码:GB2312字节数:2;编…

  • protel99se基本教程及使用教程

    protel99se基本教程及使用教程protel99se基本教程1、启动Protel99SE通常直接用桌面的快捷方式进入,双击图标即可;或者通过开始菜单由程序方式进入。其界面如图1-1所示。此时菜单栏里有四个下拉菜单选项,分别是向下的箭头项系统菜单,Files文件菜单,View视图菜单和Help帮助菜单。2、软件系统参数设置Protel99SE运行后的第一件事,必须调整参数设置,否则由于字体的问题会造成界面中的…

  • Laravel自定义 封装便捷返回Json数据格式引用

    Laravel自定义 封装便捷返回Json数据格式引用

  • 计算思维与创新创业 课程 获批

    计算思维与创新创业 课程 获批为什么80%的码农都做不了架构师?>>>…

  • C语言 neutralize函数,三种常用分子模拟软件绍.doc

    C语言 neutralize函数,三种常用分子模拟软件绍.doc三种常用分子模拟软件绍三种常用分子模拟软件介绍一、NAMD  NAMD(NAnoscaleMolecularDynamics)是用于在大规模并行计算机上快速模拟大分子体系的并行分子动力学代码。NAMD用经验力场,如Amber,CHARMM和Dreiding,通过数值求解运动方程计算原子轨迹。  1.软件所能模拟的体系的尺度,如微观,介观或跨尺度等  微观。  是众多md软件中并行处理…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号