Description
贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿，突然，牛棚的电源跳闸了，所有的灯都被关闭了。贝希是一个很胆小的女生，在伸手不见拇指的无尽的黑暗中，她感到惊恐，痛苦与绝望。她希望您能够帮帮她，把所有的灯都给重新开起来！她才能继续快乐地跟她的闺密们继续玩游戏！
牛棚中一共有N（1 <= N <= 35）盏灯，编号为1到N。这些灯被置于一个非常复杂的网络之中。有M（1 <= M <= 595）条很神奇的无向边，每条边连接两盏灯。
每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候，这盏灯本身，还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是：当一盏灯是开着的时候，这盏灯被关掉；当一盏灯是关着的时候，这盏灯被打开。
问最少要按下多少个开关，才能把所有的灯都给重新打开。
数据保证至少有一种按开关的方案，使得所有的灯都被重新打开。
牛棚中一共有N（1 <= N <= 35）盏灯，编号为1到N。这些灯被置于一个非常复杂的网络之中。有M（1 <= M <= 595）条很神奇的无向边，每条边连接两盏灯。
每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候，这盏灯本身，还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是：当一盏灯是开着的时候，这盏灯被关掉；当一盏灯是关着的时候，这盏灯被打开。
问最少要按下多少个开关，才能把所有的灯都给重新打开。
数据保证至少有一种按开关的方案，使得所有的灯都被重新打开。
Input
第一行：两个空格隔开的整数：N和M。
第二到第M+1行：每一行有两个由空格隔开的整数，表示两盏灯被一条无向边连接在一起。没有一条边会出现两次。
Output
第一行：一个单独的整数，表示要把所有的灯都打开时，最少需要按下的开关的数目。
Sample Input
5 6
1 2
1 3
4 2
3 4
2 5
5 3
Sample Output
3
做法：高斯消元解异或方程组，或折半搜索都可以过啦。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#define LL long long
using namespace std;
LL m[][];
int n, M, b[], ans, Ans[]; void Init()
{
scanf("%d%d", &n, &M);
for (int i = ; i <= n; i++)
m[i][i] = , b[i] = ;
for (int i = ; i <= M; i++)
{
int u, v;
scanf("%d%d", &u, &v);
m[u][v] = ;
m[v][u] = ;
}
} void Dfs(int dep, int count)
{
if (count >= ans) return;
if (dep == )
{
if (count < ans) ans = count;
return;
}
if (m[dep][dep])
{
bool now = b[dep];
for (int i = dep + ; i <= n; i++)
if (m[dep][i]) now ^= Ans[i];
Ans[dep] = now;
if (Ans[dep]) Dfs(dep - , count + );
else Dfs(dep - , count);
}
else
{
Ans[dep] = ; Dfs(dep - , count);
Ans[dep] = ; Dfs(dep - , count + );
Ans[dep] = ;
}
} void Swap(int l, int r)
{
for (int i = ; i <= n; i++)
swap(m[l][i], m[r][i]);
swap(b[l], b[r]);
} void Xor(int l, int r)
{
for (int i = ; i <= n; i++)
m[l][i] ^= m[r][i];
b[l] ^= b[r];
} void Work()
{
for (int k = ; k <= n; k++)
{
bool flag = ;
for (int i = k; i <= n; i++)
if (m[i][k])
{
flag = ;
Swap(i, k);
break;
}
if (flag == ) continue;
for (int i = k + ; i <= n; i++)
if (m[i][k]) Xor(i, k);
}
} int main()
{
Init();
Work();
ans = ;
Dfs(n, );
printf("%d", ans);
}
高斯消元
#include <cstdio>
#include <iostream>
#include <cstring>
#define N 40
#define M 100007
#define LL long long
using namespace std;
int n, m, tot, g[M + ], ans = M;
LL h[M + ], Ans, a[N], S[]; void Pre_work()
{
S[] = ;
for (int i = ; i <= ; i++) S[i] = S[i - ] * ;
} void Init()
{
Pre_work();
scanf("%d%d", &n, &m);
int u, v;
for (int i = ; i <= n; i++)
a[i] |= S[i];
for (int i = ; i <= m; i++)
{
scanf("%d%d", &u, &v);
a[u] |= S[v];
a[v] |= S[u];
}
Ans = S[n + ] - ;
} int Hash(LL x)
{
int p = x % M;
for (; h[p] != && h[p] != x; p = (p + ) % M);
return p;
} void Dfs(int dep, LL num, int step)
{
if (dep > tot)
{
if (num == Ans) ans = min(ans, step);
int site = Hash(num);
if (!h[site]) h[site] = num, g[site] = step;
else g[site] = g[site] < step ? g[site] : step;
return;
}
Dfs(dep + , num ^ a[dep], step + );
Dfs(dep + , num, step);
} void dfs(int dep, LL num, int step)
{
if (dep > n)
{
if (num == Ans) ans = min(ans, step);
LL p = Ans ^ num;
int site = Hash(p);
if (h[site]) ans = min(ans, g[site] + step);
return;
}
dfs(dep + , num ^ a[dep], step + );
dfs(dep + , num, step);
} int main()
{
Init();
tot = n / ;
Dfs(, , );
dfs(tot + , , );
printf("%d", ans);
}
折半搜索