Meet in the middle

我们都知道搜索是非常常用的一个东西，我们在解决不了问题的时候就会选择他来暴力寻找最优解。

一般的暴力的复杂度都是指数级，比如常见的 01 背包，复杂度就是 \(O(2^{n})\)，而如果我们用了 meet in the middle，就可以让我们的时间复杂度降到 \(O(2^{\frac{n}{2}})\)。

而他的思想也很简单，把问题从中间拆开，分成两部分来 DFS，一半是 \(1\sim \frac{n}{2}\)，一半是 \(\frac{n}{2} + 1\sim n\)。

然后在判断中间接起来的问题就可以了。

P2962 [USACO09NOV] Lights G

我们看到数据范围，只有 \(35\)，我们考虑一下状压。

我们发现一个点只有两种状态，且一个改一个点会导致周围的点也都变，所以我们可以用一个数组，里面存放二进制数，每一位代表一个编号的点，1 表示白，0 表示黑。

我们在搜索的时候和上面一样分成两部分，我们用一个 map 来记录当前状态的最少步数，然后直接搜索即可。

#include <bits/stdc++.h>

#define INF INT_MAX
#define int long long
#define N 10100

using namespace std;

int mp[N], now, n, m, ans = INF;
map<int, int> a;

inline void dfs(int x, int u, int k, int t)//u是终点，k是当前状态，t是当前点的花费 
{
	if(a[k]) a[k] = min(a[k], t);
	else a[k] = t;
	if(a[k ^ now] || k == now)
		ans = min(a[k ^ now] + t, ans);
	if(x <= u)
	{
		dfs(x + 1, u, k, t);
		k ^= mp[x];
		dfs(x + 1, u, k, t + 1);
	}
}

signed main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int u, v;
		cin >> u >> v;
		mp[u] ^= (1 << v);//处理每一个与之相连的点 
		mp[v] ^= (1 << u); 
	}
	for(int i = 1; i <= n; i ++)
	{
		mp[i] ^= (1 << i);//把每一个点都按位异或1 
		now ^= (1 << i);
	}
	dfs(1, n / 2, 0, 0);//折半搜索 
	dfs(n / 2 + 1, n, 0, 0);
	cout << ans << endl;
	return 0;
}