题意

给一张$n\times m$二分图，带点权，问有多少完美匹配子集满足权值和大于等于$t$

---

这里有一个结论：对于二分图$\mathbb{A}$和$\mathbb{B}$集合，如果子集$A \in \mathbb{A}，B \in \mathbb{B}$，且$A,B$分别是完美匹配的子集，那么$A \cup B$属于一个完美匹配

有了这个结论之后，考虑单侧，枚举子集$S$,利用霍尔定理判定$S$是否是完美匹配，并通过dp转移状态，记录下单侧所有满足条件的权值和，然后两侧一起考虑累加得到答案

时间复杂度$O((n+m)2^{max(n,m)})$

代码

#include 
    
     using namespace std;typedef long long LL;const int N = 1 << 20;int n, m, a[N + 5], b[N + 5], cnt[N + 5], L[N + 5], R[N + 5], fl[N + 5], fr[N + 5], t;char str[100][100];vector
     
       g1, g2;int main() {    scanf("%d%d", &n, &m);    for(int i = 0; i < n; ++i) scanf("%s", str[i]);    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);    for(int i = 0; i < m; ++i) scanf("%d", &b[i]);    for(int i = 0; i < n; ++i) {        for(int j = 0; j < m; ++j) {            if(str[i][j] == '1') {                L[i] |= (1 << j); R[j] |= (1 << i);            }        }    }    scanf("%d", &t);    for(int i = 0; i <= max((1 << n), (1 << m)); ++i) cnt[i] = cnt[i>>1] + (i & 1);    for(int s = 0; s < (1 << n); ++s) {        int now = 0, v = 0;        fl[s] = 1;        for(int i = 0; i < n; ++i) {            if((s >> i) & 1) {                v += a[i]; now |= L[i];                fl[s] &= fl[s ^ (1 << i)];            }        }        if(fl[s] && cnt[s] <= cnt[now]) g1.push_back(v);        else fl[s] = 0;    }    for(int s = 0; s < (1 << m); ++s) {        int now = 0, v = 0;        fr[s] = 1;        for(int i = 0; i < m; ++i) {            if((s >> i) & 1) {                v += b[i]; now |= R[i];                fr[s] &= fr[s ^ (1 << i)];            }        }        if(fr[s] && cnt[s] <= cnt[now]) g2.push_back(v);        else fr[s] = 0;    }    sort(g1.begin(), g1.end());    LL ans = 0;    for(int i = 0; i < g2.size(); ++i) {        ans += g1.size() - (lower_bound(g1.begin(), g1.end(), t - g2[i]) - g1.begin());    }    cout << ans << endl;    return 0;}/* 3 30101110101 2 38 5 1321 *//* 3 20111101 2 34 58 */