P3679 [CERC2016] 二分毯 Bipartite Blanket
考虑霍尔定理和广义霍尔定理：
霍尔定理：对于一个左部图为
X 、右部图大小为Y 的二分图（钦定|X|\leq |Y| ），存在边数等于|X| 的匹配的充要条件是：对于左部图的任何一个点集，右部图中和它相邻的点集大小都大于等于它（相邻的点集指的是所有点出边的并集）。
-
证明：必要条件显然。
可这为什么是充分条件？考虑反证法，如果我们的增广路算法在进行到某一步的时候停止了——令左部图点集为
X ，右部图点集为Y ，Z 是我们能从左部图的非匹配点在增广路图上走到的点。那么Y\cap Z 内的点都被匹配了。我们会发现X\cap Z 内的点只能走到Y\cap Z 内的点，同时X\cap Z 内有未匹配点，和霍尔定理作为必要条件这一点矛盾了。 -
此外，假设
|X|>|Y| ，这个定理就不成立了。
广义霍尔定理：给定一张二分图。如果存在一个匹配覆盖左部图中的点集
X ，且存在一个匹配覆盖右部图中的点集Y ，那么存在一个匹配同时覆盖X 和Y 。
-
证明：考虑覆盖
X 与覆盖Y 的两个匹配的异或Z （这里指边集的异或）。根据定义，满足任意一个点的度数都小于等于2 。发现这样的图中只存在独立的环或者独立的链，于是我们对两种情况分类讨论一下：-
对于一个环
由于当前二分图只有偶环，故而考虑隔一条边取一次。
-
对于一条链
如果当前是奇链，那就从一端开始隔一条边取一次。
如果当前是偶链，会发现
X\cup Y 不等于两个匹配并集的总点数（注意到X,Y 与匹配中的点是有区别的，匹配中的点包含了左部点和右部点，而X,Y 都只是“左部点和右部点”中的一种），于是我们规避掉实际上不处于X\cup Y 的点就行了。
-
根据广义霍尔定理，我们对于点集
-
判定点集
S 的合法性判断权值是否不小于
t 好做，枚举每个点判断是否在集合里，求和再与t 比较即可。判断一个点集是否被至少一个匹配包含，可以依据霍尔定理（要满足下面所述的两个条件）：
第
1 条可以直接暴力枚举+统计，第二条采用高维前缀和求解。 -
-
合并方案
对
A 的所有合法子集按照权值从小到大排序。接着枚举B 的每个合法子集，A 中能与它组成合法集合V 的子集必定是排序后的一段后缀（因为当前只需要考虑和\geq t ），可以利用双指针解决。
时间复杂度
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 22, M = (1 << 20);
int n, m, U, t, t1, t2, a[N], b[N]; ll ans;
int e1[M], e2[M], r1[M], r2[M], w1[M], w2[M], c1[M], c2[M];
void check(int a[], int e[], int w[], int c[]){
FL(s, 0, U){
FL(i, 1, n) if(s & (1 << i - 1))
w[s] += a[i], c[s] |= e[i];
c[s] = (__builtin_popcount(c[s]) >= __builtin_popcount(s));
}
FL(i, 1, n) FL(s, 0, U) if(s & (1 << i - 1))
c[s] = min(c[s], c[s ^ (1 << i - 1)]);
}
int main(){
scanf("%d%d", &n, &m);
FL(i, 1, n) FL(j, 1, m){
char ch; scanf(" %c", &ch);
e1[i] |= (ch - 48 << j - 1);
e2[j] |= (ch - 48 << i - 1);
}
FL(i, 1, n) scanf("%d", &a[i]);
FL(i, 1, m) scanf("%d", &b[i]);
scanf("%d", &t), U = (1 << (n = max(n, m))) - 1;
check(a, e1, w1, c1), check(b, e2, w2, c2);
FL(s, 0, U){
if(c1[s]) r1[++t1] = w1[s];
if(c2[s]) r2[++t2] = w2[s];
}
sort(r1 + 1, r1 + t1 + 1);
sort(r2 + 1, r2 + t2 + 1);
int j = t2 + 1;
FL(i, 1, t1){
while(j > 1 && r2[j - 1] + r1[i] >= t) j--;
ans += t2 - j + 1;
}
printf("%lld\n", ans);
return 0;
}