奇技淫巧了解一下...... 关键词:高斯消元   深度优先搜索DFS 相关题目:[USACO09NOV]灯Lights

O2优化

题目描述

贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏! 牛棚中一共有N(1 <= N <= 35)盏灯,编号为1到N。这些灯被置于一个非常複杂的网络之中。有M(1 <= M <= 595)条很神奇的无向边,每条边连接两盏灯。 每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候,这盏灯本身,还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是:当一盏灯是开著的时候,这盏灯被关掉;当一盏灯是关著的时候,这盏灯被打开。 问最少要按下多少个开关,才能把所有的灯都给重新打开。 数据保证至少有一种按开关的方案,使得所有的灯都被重新打开。

输入输出格式

输入格式:

  • 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.

输出格式:

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

样例输入:

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

样例输出:

3

分析及解决

  • 折半搜索 < meet in the middle >

折半搜索就是先暴搜出前一半状态并记录 217 ,再搜后一半状态。后一半状态结束时利用前一半状态的记录更新答案。(详见代码)

亲测 unordered_mapmap 稍快......

2018.04.12

  • 正解:高斯消元

首先,我们注意到一点,一盏灯的开关至多按一次。根据题意,我们可以列出 nn 元异或方程组。 比如说我们可以设每一盏灯的开关的状态为 x1,x2,...xnx_{1},x_{2},...x_{n} (即是否按)。对于灯 aa 和灯 bb 是否连接用 mat[a][b]mat[a][b] 表示。于是得到方程组:

  • TeX parse error: Undefined control sequence \[

    (保证每盏灯最后都是亮的)

  • TeX parse error: Undefined control sequence \[

......

  • TeX parse error: Undefined control sequence \[

那么进行 高斯消元 就好了。要注意因为有些灯可能可按可不按,所以消元完成后可能会有多种答案。那么最后 暴搜 自由元就好了......

2018.04.21

AC代码

折半搜索 meet in the middle unordered_map 最慢点 Time:28ms / Memory:8250KB -O2 map 最慢点 Time:44ms / Memory:9746KB -O2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio> 
#include<unordered_map>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define min(a,b) ((a)<(b)?(a):(b))
#define INF 0x3f3f3f3f
int n, m, cnt, ans=INF;
long long _2[40], res[40];
long long kkk;
unordered_map<long long,int> mp;

inline void dfs(int now, long long p, int used, int f) {
if(now==cnt+1) {
if(p==kkk) ans=min(ans, used);
else {
if(f) {
int tmp = mp[p];
if(!tmp || tmp>used) mp[p] = used;
}
else {
int tmp = mp[kkk^p];
if(tmp) ans=min(ans, tmp+used);
}
}
return ;
}
dfs(now+1, p^res[now], used+1, f), dfs(now+1, p, used, f);
}

inline void mim() {
cnt = n/2;
dfs(1,0,0,1);
cnt = n;
dfs(n/2+1,0,0,0);
printf("%d\n", ans);
} // meet in the middle
int main(){
scanf("%d%d", &n, &m);
_2[0] = 1; rep(i,1,n) _2[i] = _2[i-1]<<1;
kkk = _2[n]-1;
re u, v;
rep(i,1,m) {
scanf("%d%d", &u, &v);
res[u] |= _2[v-1], res[v] |= _2[u-1];
}
rep(i,1,n) res[i] |= _2[i-1];
mim();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <memory>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define min(a,b) ((a)<(b)?(a):(b))

int n, m, mat[40][40];
int res, xx, ans[40];

inline void Gauss() {
rep(i,1,n) {
int j=i;
while(j<=n && !mat[j][i]) ++j;
if(j>n) continue; //该元的解不唯一
if(i!=j)
rep(k,i,n+1) std::swap(mat[i][k], mat[j][k]);
rep(j,1,n)
if(i!=j && mat[j][i])
rep(k,i,n+1) mat[j][k]^=mat[i][k];
}
}

inline void dfs(int now) {
if(xx>=res) return ;
if(!now) {
res=min(res, xx);
return ;
}
if(mat[now][now]) {
int x=mat[now][n+1];
rep(i,now+1,n)
if(mat[now][i]) x^=ans[i];
ans[now]=x;
xx+=x;
dfs(now-1);
xx-=x;
}
else {
ans[now]=0, dfs(now-1);
ans[now]=1, ++xx, dfs(now-1), --xx;
}
}

int main() {
scanf("%d%d", &n, &m);
rep(i,1,n) mat[i][i]=1, mat[i][n+1]=1;
re u, v;
rep(i,1,m) {
scanf("%d%d", &u, &v);
mat[u][v]=mat[v][u]=1;
} // 构造异或方程组
res=n, xx=0;
Gauss();
dfs(n);
printf("%d\n", res);
}