当前位置:网站首页>HDU 4337 King Arthur's Knights 它输出一个哈密顿电路
HDU 4337 King Arthur's Knights 它输出一个哈密顿电路
2022-07-06 19:36:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
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;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116761.html原文链接:https://javaforall.cn
边栏推荐
- 从控制理论的角度谈数据分析
- 密码学系列之:在线证书状态协议OCSP详解
- Redis Getting started tutoriel complet: positionnement et optimisation des problèmes
- 杰理之开启经典蓝牙 HID 手机的显示图标为键盘设置【篇】
- Cglib agent in agent mode
- How to find file accessed / created just feed minutes ago
- 2022 spring recruitment begins, and a collection of 10000 word interview questions will help you
- Oracle中日期的使用方法实例
- 代码调试core-踩内存
- Babbitt | metauniverse daily must read: is IP authorization the way to break the circle of NFT? What are the difficulties? How should holder choose the cooperation platform
猜你喜欢
Django database (SQLite) basic introductory tutorial
NuScenes数据集关于Radar数据的统计
Construction of knowledge map of mall commodities
Kysl Haikang camera 8247 H9 ISAPI test
Redis入门完整教程:复制配置
AWS learning notes (I)
How to design interface test cases? Teach you a few tips to draft easily
如何分析粉丝兴趣?
The 8 element positioning methods of selenium that you have to know are simple and practical
How to analyze fans' interests?
随机推荐
A complete tutorial for getting started with redis: AOF persistence
C language exercises_ one
How-PIL-to-Tensor
Uniapp adaptation problem
Cglib agent in agent mode
Unity使用MaskableGraphic画一条带箭头的线
Analysis of USB network card sending and receiving data
左程云 递归+动态规划
[node learning notes] the chokidar module realizes file monitoring
[2022 national tournament simulation] polygon - computational geometry, binary answer, multiplication
哈希表及完整注释
Shell 编程基础
Summary of research status of inertial navigation calibration at home and abroad (abridged version)
Error: could not find a version that satisfies the requirement xxxxx (from versions: none) solutions
C language string sorting
Unity custom webgl packaging template
New benchmark! Intelligent social governance
uniapp的表单验证
商城商品的知识图谱构建
sshd[12282]: fatal: matching cipher is not supported: [email protected] [preauth]