哈密顿回路

Time Limit: 15 Sec Memory Limit: 256 MB

Description

给定一张 n个点的边带权的无向完全图，求图中是否存在一条长为L的哈密顿回路。
哈密顿回路：从起点出发经过所有点恰好一次并最终回到起点(起点头尾经过两次)的路径。

Input

img

Output

img

Sample Input

4 10
　　0 3 2 1
　　3 0 1 3
　　2 1 0 2
　　1 3 2 0

Sample Output

possible

img

HINT

img

Main idea

判断能否找到一条长度为L的哈密顿回路。

Solution

我们直接使用Meet in middle，记录M[t][opt]表示以 t 结尾，到的点为 opt 的长度集合。然后暴力合并即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 230;
const int Base = 10007;
const int INF = 2147483640;

int n;
int lenA,lenB;
s64 E[15][15];
int Num[ONE],vis[ONE],a[ONE];
s64 Ans,L;

vector <s64> M[15][1<<15];

int get()
{
    int res=1,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Dfs(int u,int opt,int T,s64 Val)
{
    if( Val > L) return;
    if( T==lenA || T==lenB ) M[u][opt].push_back(Val);
    if( T==max(lenA,lenB) ) return;
    for(int v=1; v<=n; v++)
    {
        int now = opt | (1<<v-1);
        if(now != opt) Dfs(v,now,T+1,Val+E[u][v]);
    }
}

int main()
{
    n=get();    cin>>L;
    lenA = (n+2)/2;        lenB = (n+2)-lenA;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            scanf("%lld",&E[i][j]);
        }

    Dfs(1,1,1,0);

    int All = (1<<n)-1;

    for(int u=1;u<=All;u++)
        for(int t=1;t<=n;t++)
            sort(M[t][u].begin(),M[t][u].end());

    for(int u=1;u<=All;u++)
        for(int t=1;t<=n;t++)
        {
            if(! (u&(1<<t-1)) ) continue;
            int v = All^u |1 | (1<<t-1);
            int A_size = M[t][u].size(), B_size = M[t][v].size()-1;
            for(int i=0;i<A_size;i++)
            {
                s64 A = M[t][u][i];

                while(B_size >= 0 && M[t][v][B_size] + A > L) B_size--;
                if(B_size < 0) break;
                if(M[t][v][B_size] + A == L)
                {
                    printf("possible");
                    exit(0);
                }
            }
        }

    printf("impossible");
}