设计网站大全软件,做网站百度收录,海口建设局网站,河南省城乡住房建设厅网站题意#xff1a;
有 n盏灯#xff0c;每盏灯与若干盏灯相连#xff0c;每盏灯上都有一个开关#xff0c;如果按下一盏灯上的开关#xff0c;这盏灯以及与之相连的所有灯的开关状态都会改变。一开始所有灯都是关着的#xff0c;你需要将所有灯打开#xff0c;求最小的按…题意
有 n盏灯每盏灯与若干盏灯相连每盏灯上都有一个开关如果按下一盏灯上的开关这盏灯以及与之相连的所有灯的开关状态都会改变。一开始所有灯都是关着的你需要将所有灯打开求最小的按开关次数。(1n35)。
题目
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…M1: 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(2n)O(2^{n})O(2n) , 显然超时。不过如果我们用 meet in middle 的话时间复杂度可以优化至O(n2n2)O(n2^{\frac{n}{2}})O(n22n) 。 2.meet in middle 就是让我们先找一半的状态也就是找出只使用编号为 1到 mid的开关能够到达的状态再找出只使用另一半开关能到达的状态。 3.如果前半段和后半段开启的灯互补将这两段合并起来就得到了一种将所有灯打开的方案。 4.具体实现时可以把前半段的状态以及达到每种状态的最少按开关次数存储在 map 里面搜索后半段时每搜出一种方案就把它与互补的第一段方案合并来更新答案。
AC代码
#include algorithm
#include cstdio
#include iostream
#include mapusing namespace std;typedef long long ll;int n, m, ans 0x7fffffff;
mapll, 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;
}
