相似题求条
查看原帖
相似题求条
772875
RAY091016楼主2025/7/3 20:04

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;
}

2025/7/3 20:04
加载中...