Meet In The Middle

Published: by Creative Commons Licence

  • Tags:

Meet In The Middle

考虑这样一个问题,我们有一个大小为N($N\leq 40$)的集合S,我们希望找到一个它的子集,使得子集的和在小于M($M\leq 10^{18}$)的前提下尽可能大。

像这种问题,如果M比较小,可以用动态规划解决,如果N比较小可以用暴力枚举解决。但是现在我们两种方式都用不了。

Meet In the middle是一种非常简单的思路,将集合分成大小尽可能接近的两个不相交子集A、B。之后我们容易发现结果要么是A的子集,要么是B的子集,要么是A的某个子集和B的某个子集的并。

我们直接暴力解决是单个集合子集的情况,时间复杂度为$2^{\frac{N}{2}}$。之后我们维护这两部分信息,并合并解决跨子集部分。在这里我们可以用提前对A和B的子集的总和排序,并双指针技术在线性时间内找到最大跨越A、B的子集和。总的时间空间复杂度为$O(2^{\frac{N}{2}})$。

例子1

一个拥有最多40个顶点的无向图中,统计最大独立集的大小。

可以用Meet In The Middle加上FWT算法解决。总的时间复杂度为 \(O(\frac{N}{2}\cdot 2^{\frac{N}{2}})\) 。

例子2

一个拥有最多40个顶点的无向图中,统计独立集的数目。

同例子1。

Codeforces1221G

题意

https://codeforces.com/contest/1221/problem/G

题解

很容易想到用容斥解决。

  • 边权非0(2):

但是问题是所有边权不能为0(2),代表的是任意两个点权为0(1)的顶点之间不能出现边。即点权为0的顶点组成的集合是一个独立集,而方案数正好等于独立集合的数目。但是统计独立集的数目我们需要用二进制掩码进行统计,需要的时间是$O(2^n)$,这里n能取到40,所以是不现实的。后来发现有Meet In The Middle技术,可以将时间复杂度和空间复杂度降低至$O(2^{\frac{n}{2}})$。

  • 边权非1:

这个对应的就是每个连通块的点权都是相同的方案数。

  • 边权非0且非1(非1且非2)

即边权必须为2(0),这意味着每条边的两端的点权都必须是1(0),只有那些度数为0的顶点的点权可以任意选择。

  • 边权非0且非2

即边权为1,即任意边的两端一个是1,一个是0。因为不同连通块是独立统计的,先考虑统计同一连通块。如果连通块是二分图,那么就能提供两种选择,否则就只能提供0种选择。将选择数累乘起来即可。

  • 边权非1且非2且非3

只有在没有边的情况下存在,如果没有边,所有顶点的着色都有两种可能。

CF1257F

题意

https://codeforces.com/contest/1257/problem/F

题解

就是Meet in middle的裸题。将结果分成前15位和后15位,分别处理,之后用哈希表实现线性查找即可。