我们都知道搜索是非常常用的一个东西，我们在解决不了问题的时候就会选择他来暴力寻找最优解。
一般的暴力的复杂度都是指数级，比如常见的 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;
}