题解 | Lights-牛客假日团队赛12K题
Lights
https://ac.nowcoder.com/acm/contest/1081/K
题目描述
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.
输入描述:
* 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.
示例1
输入
5 6
1 2
1 3
4 2
3 4
2 5
5 3
输出
3
说明
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.
解答
状压，时间空间都不行，如果每次搜索一半就可以省下很多空间，用map记下每种状态的答案，最后再把两次的答案合并
然而正解是高斯消元解异或方程组，最后搜索自由元
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
const int maxn=40;
const int maxm=600;
int n,m,p,ans=36,fl;
ll f[maxn];
map<ll,int>mx;//每种状态的最小代价
void dfsl(int x,ll s,int k){
if(x==m){
int &t=mx[s];//注意传址的引用
if(!t)t=k;
else if(t>k)t=k;
return;
}
dfsl(x+1,s,k);
dfsl(x+1,s^f[x],k+1);
}
void dfsr(int x,ll s,int k){
if(x==m){
int t=mx[s];
if(t && t+k-1<ans)ans=t+k-1;
return;
}
dfsr(x+1,s,k);
dfsr(x+1,s^f[x+m],k+1);
}
int main(){
scanf("%d%d",&n,&p);
if(n&1)n++,fl=1;//处理折半搜索
m=n/2;
for(int i=1,x,y;i<=p;i++){
scanf("%d%d",&x,&y);
x--,y--;
f[x]|=1LL<<y,f[y]|=1LL<<x;
}
for(int i=0;i<n;i++)f[i]|=1LL<<i;
dfsl(0,(1LL<<n)-1,1);
dfsr(0,0,0);
printf("%d",ans-fl);
} 来源：weixin_30522183
