Description
一个图,对一个点进行操作会改变这个点及其相邻的点的状态,问全部变成黑色至少需要几次.数据保证有解.
Sol
Meet in middle.
我一开始写个高斯消元,发现有两个点过不去,原因是没有处理好*元,应该在DFS的时候回带所有解,然后就弃疗了.
然后发现这个其实可以暴力,就是 Meet in middle...
先把前一半暴力枚举存到 map 里,后一半再枚举,从 map 中找补集.
复杂度 \(O(2^{13})\)
Code
/**************************************************************
Problem: 1770
User: BeiYu
Language: C++
Result: Accepted
Time:416 ms
Memory:5384 kb
****************************************************************/ #include <cstdio>
#include <map>
#include <iostream>
using namespace std; typedef long long LL;
const int N = 40; int n,m,ans=N;
LL state,pow2[N],a[N];
map< LL,int > mp; void DFS1(int l,int r,int w,LL s){
if(l>r){ if(mp.find(s)==mp.end() || mp[s]>w) mp[s]=w;return; }
DFS1(l+1,r,w,s);
DFS1(l+1,r,w+1,s^a[l]);
}
void DFS2(int l,int r,int w,LL s){
if(l>r){ if(mp.find(state^s)!=mp.end()) ans=min(ans,w+mp[state^s]);return; }
DFS2(l+1,r,w,s);
DFS2(l+1,r,w+1,s^a[l]);
}
int main(){
cin>>n>>m;
pow2[0]=1LL;
for(int i=1;i<=n;i++) pow2[i]=pow2[i-1]<<1;
for(int i=0;i<n;i++) a[i]|=pow2[i],state|=pow2[i];
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
u--,v--;
a[u]|=pow2[v],a[v]|=pow2[u];
}
DFS1(0,min(n-1,n/2),0,0);
DFS2(min(n-1,n/2)+1,n-1,0,0);
cout<<ans<<endl;
return 0;
}