rt,不同之处为初始状态给定
code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,ans=1e9,p[50],s,op;
map<int,int>f;
signed main(){
cin>>n>>m;
p[0]=1;
for(int i=1;i<n;i++){
p[i]=p[i-1]<<1;
}
for(int i=1;i<=n;i++){
cin>>op;
s|=(op*(1ll<<(i-1)));
}
for(int i=1;i<=m;i++){
cin>>x>>y;
x--,y--;
p[x]|=(1ll<<y);
p[y]|=(1ll<<x);
}
for(int i=0;i<(1<<(n/2));i++){
int cnt=0,t=s;
for(int j=0;j<n/2;j++){
if((i>>j)&1){
cnt++;
t^=p[j];
}
}
if(f.count(t)){
f[t]=min(f[t],cnt);
}
else{
f[t]=cnt;
}
}
for(int i=0;i<(1<<(n-n/2));i++){
int cnt=0,t=s;
for(int j=0;j<n-n/2;j++){
if((i>>j)&1){
cnt++;
t^=p[n/2+j];
}
}
if(f.count(((1ll<<n)-1)^t)){
ans=min(ans,cnt+f[((1ll<<n)-1)^t]);
}
}
cout<<ans;
return 0;
}