題意：

有 n盞燈，每盞燈與若干盞燈相連，每盞燈上都有一個開關，如果按下一盞燈上的開關，這盞燈以及與之相連的所有燈的開關狀態都會改變。一開始所有燈都是關著的，你需要將所有燈打開，求最小的按開關次數。(1<=n<=35)。

題目：

Bessie and the cows were playing games in the barn, but the power was reset and the lights were all turned off. Help the cows get all the lights back on so they can resume their games.

The N (1 <= N <= 35) lights conveniently numbered 1…N and their switches are arranged in a complex network with M (1 <= M <= 595) clever connection between pairs of lights (see below).

Each light has a switch that, when toggled, causes that light – and all of the lights that are connected to it – to change their states (from on to off, or off to on).

Find the minimum number of switches that need to be toggled in order to turn all the lights back on.

It’s guaranteed that there is at least one way to toggle the switches so all lights are back on.

Input format

Line 1: Two space-separated integers: N and M.
Lines 2…M+1: Each line contains two space-separated integers representing two lights that are connected. No pair will be repeated.

Output format

Line 1: A single integer representing the minimum number of switches that need to be flipped in order to turn on all the lights.

Explanation

There are 5 lights. Lights 1, 4, and 5 are each connected to both lights 2 and 3.

Toggle the switches on lights 1, 4, and 5.

輸入

5 6
1 2
1 3
4 2
3 4
2 5
5 3

輸出

3

分析：

1.如果這道題暴力 DFS 找開關燈的狀態，時間復雜度就是$O(2^n)$ , 顯然超時。不過，如果我們用 meet in middle 的話，時間復雜度可以優化至$O(n{2}^{\frac{n}{2}})$ 。
2.meet in middle 就是讓我們先找一半的狀態，也就是找出只使用編號為 1到 mid的開關能夠到達的狀態，再找出只使用另一半開關能到達的狀態。
3.如果前半段和后半段開啟的燈互補，將這兩段合并起來就得到了一種將所有燈打開的方案。
4.具體實現時，可以把前半段的狀態以及達到每種狀態的最少按開關次數存儲在 map 里面，搜索后半段時，每搜出一種方案，就把它與互補的第一段方案合并來更新答案。

AC代碼：

#include <algorithm> #include <cstdio> #include <iostream> #include <map>using namespace std;typedef long long ll;int n, m, ans = 0x7fffffff; map<ll, int> f; ll a[40]; int main() {cin >> n >> m;for (int i = 0; i < n; ++i)a[i] = (1ll << i);for (int i = 1; i <= m; ++i){int u, v;cin >> u >> v;--u;--v;a[u] |= (1ll << v);a[v] |= (1ll << u);}for (int i = 0; i < (1 << (n / 2)); ++i){ll t = 0;int cnt = 0;for (int j = 0; j < n / 2; ++j){if ((i >> j) & 1){t ^= a[j];++cnt;}}if (!f.count(t))f[t] = cnt;elsef[t] = min(f[t], cnt);}for (int i = 0; i < (1 << (n - n / 2)); ++i){ll t = 0;int cnt = 0;for (int j = 0; j < (n - n / 2); ++j){if ((i >> j) & 1){t ^= a[n / 2 + j];++cnt;}}if (f.count(((1ll << n) - 1) ^ t))ans = min(ans, cnt + f[((1ll << n) - 1) ^ t]);}cout << ans;return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的折半搜索+洛谷 P2962 [USACO09NOV]Lights G的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。