[USACO09NOV]Lights G

题目背景

English Edition

题目描述

给出一张 \(n\) 个点 \(m\) 条边的无向图，每个点的初始状态都为 \(0\)。

你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由 \(0\) 变成 \(1\) 或由 \(1\) 变成 \(0\)。

你需要求出最少的操作次数，使得在所有操作完成之后所有 \(n\) 个点的状态都是 \(1\)。

输入格式

第一行两个整数 \(n, m\)。

之后 \(m\) 行，每行两个整数 \(a, b\)，表示在点 \(a, b\) 之间有一条边。

输出格式

一行一个整数，表示最少需要的操作次数。

样例 #1

样例输入 #1

5 6 
1 2 
1 3 
4 2 
3 4 
2 5 
5 3

样例输出 #1

3

提示

对于 \(100\%\) 的数据，\(1\le n\le35,1\le m\le595, 1\le a,b\le n\)。

核心思路

首先我们知道如果暴力搜索的话那么时间复杂度就是\(O(2^{35}=3e10)\).肯定是会超时的，所以我们可以采用双向搜索，也就是先搜索出前一半的答案，然后再对照我们预处理出来的前一半的答案来来搜索出来我们最终所需要的答案。也就是\(O(2^{17}=1e5)\).这个时间复杂度就可以过了。

然后就是一个状态压缩的过程，我们把开的状态置为1，关的状态置为0.然后我们枚举出来所有的状态，对每一个状态进行相对应的操作。

// Problem: P2962 [USACO09NOV]Lights G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2962
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

map<int,int> f;

signed main()
{
int n,m;
cin>>n>>m;
vector<int> a(n+1);
a[0]=1;
int ans=0x3f3f3f3f;
/*
这里的a数组只是为了处理出来像题目要求的这种关联的状态。
*/
for(int i=1;i<n;i++)
a[i]=a[i-1]*2;
while(m--)
{
	int u,v;
	cin>>u>>v;
	u--;
	v--;//千万要注意因为我们的状态的下标从0开始,相当于全体都向左移动了一个单位。
	a[u]|=((int)1<<v);
	a[v]|=((int)1<<u);
}
//搜索前一半状态。

for(int i=0;i<(1<<(n/2));i++)//枚举所有的可能的状态类似于搜索把。
{
	int t=0;
	int cnt=0;//cnt表示的是我们达到这个状态所需要的操作数。
for(int j=0;j<(n/2);j++)
{
	if((i>>j)&1)//那我们就打开相对应的开关.因为我们想要i的第j为是1.
	{
		t^=a[j];
		cnt++;
	}
}
if(!f.count(t))
{
	f[t]=cnt;
}
else
 f[t]=min(f[t],cnt);
 }

//搜索后一半状态。
for(int i=0;i<(1<<(n-n/2));i++)
{
	int t=0;
	int cnt=0;
	for(int j=0;j<(n-n/2);j++)
	{
		if((i>>j)&1)
		{
			t^=a[n/2+j];
			cnt++;
		}
	}
	if(f.count((((int)1<<n)-1)^t))
	ans=min(ans,cnt+f[(((int)1<<n)-1)^t]);	
}
cout<<ans<<endl;

}