首页 > 代码库 > UVALIVE 2954 Task Sequences
UVALIVE 2954 Task Sequences
竞赛图:图中的任意两点间有且仅有一条有向弧连接
求竞赛图中的哈密顿路的算法：
首先,由数学归纳法可证竞赛图在n>=2时必存在哈密顿路；
(1)n=2时显然；
(2)假设n=k时,结论成立,哈密顿路为V1,V2,...,Vi,...,Vk；
现添加第k+1个结点，若存在弧<Vi,Vk+1>和弧<Vk+1,Vi+1>，则可得哈密顿回路V1,V2,...,Vi,Vk+1,Vi+1,...,Vk；
若不存在上述的vi,考虑到Vk+1与v1~vk的连通状况,则只有下面种原哈密顿路的情况：
1.所有的Vi(1<i<k)与Vk+1的弧的方向都是<Vi,Vk+1>，那么可得哈密顿回路V1,V2,...,Vi,...,Vk,Vk+1；
2.所有的Vi(1<i<k)与Vk+1的弧的方向都是<Vk+1,Vi>，那么可得哈密顿回路Vk+1,V1,V2,...,Vi,...,Vk；
3.存在一个中间结点m，使得所有的Vi(1<=i<=m)与Vk+1的弧方向为<Vk+1,Vi>,所有的
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 1010int next[MAXN],head;string res;int pick[MAXN][MAXN];int N;int main(){ while (cin >> N) { memset(next,0,sizeof(next)); getline(cin,res); for (int i = 1; i <= N; i++) { getline(cin,res); for (int j = 1; j <= N; j++) pick[i][j] = res[(j -1) * 2] - ‘0‘; } head = 1; int tmp; for (int k = 2; k <= N; k++) { bool found =false; for (int i = head; i ; i = next[i]) { if (pick[k][i]) { if (i == head) head = k; else next[tmp] = k; next[k] = i; found = true; break; } else tmp = i; } if (!found) next[tmp] = k; } cout << "1" << endl << N << endl; for (int i = head; i ; i = next[i]) { if (i == head) cout << i; else cout << ‘ ‘ << i; } cout << endl; } return 0;}
Vj(m<j<=k)与Vk+1的弧的方向为<Vj,Vk+1>，这时依然可以构造哈密顿路 V1,V2,...,Vi,...,Vk,Vk+1；
UVALIVE 2954 Task Sequences
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。