考虑霍尔定理和广义霍尔定理：
霍尔定理：对于一个左部图为 \(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\) 的点就行了。
-
根据广义霍尔定理，我们对于点集 \(A\) 与点集 \(B\) 单独考虑合法性，然后再合并方案即可。
-
判定点集 \(S\) 的合法性
判断权值是否不小于 \(t\) 好做，枚举每个点判断是否在集合里，求和再与 \(t\) 比较即可。
判断一个点集是否被至少一个匹配包含，可以依据霍尔定理（要满足下面所述的两个条件）：
- \(|S|\) 不大于 \(S\) 的相邻节点集合
- \(S\) 的所有子集满足第 \(1\) 条
第 \(1\) 条可以直接暴力枚举+统计，第二条采用高维前缀和求解。
-
合并方案
对 \(A\) 的所有合法子集按照权值从小到大排序。接着枚举 \(B\) 的每个合法子集，\(A\) 中能与它组成合法集合 \(V\) 的子集必定是排序后的一段后缀（因为当前只需要考虑和 \(\geq t\)），可以利用双指针解决。
时间复杂度 \(O(n2^n+m2^m)\)。
点击查看代码
#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;
}