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.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

#define MAXN 1010

int next[MAXN],head;

string res;

int pick[MAXN][MAXN];

int N;

int main()

{

        while (cin >> N)

        {

                memset(next,,sizeof(next));

                getline(cin,res);

                for (int i =  ; i <= N; i++)

                {

                        getline(cin,res);

                        for (int j = ; j <= N; j++)

                           pick[i][j] = res[(j -) * ] - '';

                }

                head = ;

                int tmp;

                for (int k = ; 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 << "" << endl << N << endl;

                for (int i = head; i ; i = next[i])

                {

                        if (i == head) cout << i;

                        else cout << ' ' << i;

                }

                cout  << endl;

        }

        return ;

}

Vj(m<j<=k)与Vk+1的弧的方向为<Vj,Vk+1>，这时依然可以构造哈密顿路 V1,V2,...,Vi,...,Vk,Vk+1；