2020.4.16 省选模拟试题 T2 哈密顿回路折半搜索 + meet in the middle

题目描述

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

输入格式

第一行两个正整数 $n,L$ 表示图的点数与期望的路径长度。点从 $1$ ~ $n$ 编号。
接下来 $n$ 行每行 $n$ 个整数，第 $i$ 行的第 $j$ 个整数 $d_{i,j}$ 表示第 $i$ 个点与第 $j$ 个点间边的长度。

输出格式

若存在则输出 “possible”，否则输出 “impossible”（均不含引号）。

样例1

possible

样例 $1$ 解释
路径为： $2->4->3->1->2；$ 路径长度为： $3+2+2+3=10；$

样例2

impossible

约定

本题采用捆绑测试。
对于所有测试点， $1\leq d_{i,j}(i\neq j) \leq L \leq 10^{15},d_{i,i}=0,d_{i,j}=d_{j,i},d_{i,j}\leq d_{i,k}+d_{k,j}$
$SubTask1(30\ points):2\leq n\leq 10$
$SubTask3(30\ points):2\leq n\leq 13$
$SubTask4(40\ points):2\leq n\leq 14$

题解

折半搜索 + $meet\ in\ the\ middle$
由于最终一定是一个回路，所以假设从点 $1$ 开始搜索
搜到一半即可，然后将搜到的路径长度放到 $vector$ 或 $map$ 中进行两端对接
考虑对接的时候，如果我们知道某个路径的起点和终点
则将边权相加即为回路长度
假设一端为 $1$ ，在对接时暴力枚举另一端及路径上的点的二进制状态
对接时 $meet\ in\ the\ middle$ 即可
时间复杂度：
设一半点数为 $d$ ，则搜索状态总数为 $A(n,d)$ ≈ $17297280$
合并的复杂度为 $2^{d} * n * 2^{d}$ ≈ $196608$
搜索时加上剪枝即可

code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
typedef long long LL;
const int N = 15;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch^48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
int n, lena, lenb;
LL L, e[N][N];
vector <LL> m[N][1 << N];
void dfs(int x, int sta, int t, LL val) {
	if(val > L) return;
	if((t == lena + 1) || (t == lenb + 1)) m[x][sta].push_back(val);
	if(t == lena + 1) return;
	for(int i = 1; i <= n; ++ i) {
		int now = sta | (1 << (i - 1));
		if(now != sta) dfs(i, now, t + 1, val + e[x][i]);
	}
}
signed main() {
//	freopen("hamilton.in", "r", stdin);
//	freopen("hamilton.out", "w", stdout);
	n = read(); L = read(); lena = n / 2; lenb = n - lena;
	if(lena < lenb) swap(lena, lenb);
	for(int i = 1; i <= n; ++ i) for(int j = 1; j <= n; ++ j) e[i][j] = read();
	dfs(1, 1, 1, 0);
	for(int i = 1; i < (1 << n); ++ i) for(int j = 1; j <= n; ++ j) sort(m[j][i].begin(), m[j][i].end());
	for(int i = 1; i < (1 << n); ++ i) {
		for(int j = 1; j <= n; ++ j) {
			if(! (i & (1 << (j - 1)))) continue;
			int v = (((1 << n) - 1) ^ i) | 1 | (1 << (j - 1));
			int sizea = m[j][i].size() - 1, sizeb = m[j][v].size() - 1;
			for(int k = 0; k <= sizea; ++ k) {
				while(sizeb >= 0 && m[j][v][sizeb] + m[j][i][k] > L) sizeb --;
				if(sizeb < 0) break;
				if(m[j][v][sizeb] + m[j][i][k] == L) return puts("possible"), 0;
			}
		}
	}
	puts("impossible");
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
4 10
0 3 2 1
3 0 1 3
2 1 0 2
1 3 2 0

3 5
0 1 2
1 0 3
2 3 0

10 22
0 3 2 1 3 2 1 3 2 1 
3 0 1 3 2 1 3 2 1 3
2 1 0 2 3 2 1 3 2 1
1 3 2 0 3 2 1 3 2 1 
3 2 3 3 0 4 3 2 1 1
2 1 2 2 4 0 3 2 2 3
1 3 1 1 3 3 0 1 2 1
3 2 3 3 2 2 1 0 3 2
2 1 2 2 1 2 2 3 0 1
1 3 1 1 1 3 1 2 1 0
*/