USACO09NOV Lights G（meet in the middle）

本文主要是介绍USACO09NOV Lights G（meet in the middle），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷P2962 [USACO09NOV] Lights G

题目大意

有一个有$n$个点$m$条边的无向图，每个点的初始状态为$0$。

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

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

$1\le n\le 35,1\le m\le 595$

题解

前置知识：折半搜索（meet in the middle）

我们可以用$v_x$存储对$x$进行操作之后会改变的点，$v_x$每个二进制位表示每个点的状态，二进制位为$1$表示会改变，为$0$表示不会改变。

我们发现，每个点最多修改一次（修改两次相当于不修改）。那我们枚举每个点是否修改，最后判断这个图是否满足题意，满足的话就更新答案。这样做的书剑复杂度是$O(2^n)$的。

我们考虑用折半搜索，分别搜索$1$到$n/2$，$n/2+1$到$n$的状态，如果两种状态合并后的状态中每个点都为$1$，则当前花费就是到达两种状态的花费之和，用当前花费更新答案即可。

每种状态的最小花费可以用$map$来保存，每次修改和查询的时间复杂度为$O(\log 2^n)$，也就是$O(n)$。

总时间复杂度为$O(n{2}^{n/2})$。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=10000;
long long all=0,v[45];
map<long long,int>mp;
void dfs(int t,int to,long long s,int now){if(!mp.count(s)) mp[s]=now;else mp[s]=min(mp[s],now);if(mp[s^all]||s==all){ans=min(ans,mp[s^all]+now);}if(t<=to){dfs(t+1,to,s,now);dfs(t+1,to,s^v[t],now+1);}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);v[x]^=(1ll<<y);v[y]^=(1ll<<x);}for(int i=1;i<=n;i++){v[i]^=(1ll<<i);all^=(1ll<<i);}dfs(1,n/2,0,0);dfs(n/2+1,n,0,0);printf("%d",ans);return 0;
}

这篇关于USACO09NOV Lights G（meet in the middle）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---