题目大意

题目描述

在二分图中，所有点被划分成了两个不相交的集合 $A$ 和 $B$，每条边都恰好连接着某个 $A$ 和某个 $B$。一个匹配是一个边集，满足没有任何两条边有相同的端点。我们称一个匹配 $M$ 覆盖了点集 $V$ 当且仅当 $V$ 中的每个点都是 $M$ 中至少一条边的端点。

给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。

给定一个参数 $t$，请统计有多少点集 $V$，满足 $V$ 的权值不小于 $t$，且 $V$ 被至少一个匹配 $M$ 覆盖。

输入格式

第一行包含两个正整数 $n,m$，分别表示 $A$ 集合的点数和 $B$ 集合的点数。

接下来 $n$ 行，每行 $m$ 个 01 字符，其中第 $i$ 行第 $j$ 列为 $1$ 表示 $A_i$ 和 $B_j$ 之间有一条边。

接下来一行包含 $n$ 个正整数 $v_1,v_2,\cdots,v_n$，分别表示 $A$ 中每个点的权值。

接下来一行包含 $m$ 个正整数 $w_1,w_2,\cdots,w_m$，分别表示 $B$ 中每个点的权值。

最后一行包含一个正整数 $t$，表示参数 $t$。

输出格式

输出一行一个整数，即满足条件的点集个数。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

$1\leq n,m\leq 20$，$1\leq v_i,w_i\leq 10^7$，$1\leq t\leq 4\times 10^8$。

解题思路

那么其实这道题是一个非常重要的定理的应用，他们就是 霍尔定理 和 广义霍尔定理 。这两个定理的证明详见附录，首先我们来快速上手一下这个定理的大致内容。

霍尔定理

对于一个左部图为 $X$、右部图大小为 $Y$ 的二分图（钦定 $∣X∣≤∣Y∣$），存在边数等于 $∣X∣$ 的匹配的充要条件是：对于左部图的任何一个点集，右部图中和它相邻的点集大小都大于等于它（相邻的点集指的是所有点出边的并集）。

这一个定理的作用大概是：我们有一个方式可以让我们快速判断在一个二分图中是否存在一个完全覆盖点集 $X$ 的匹配。其中 $X$ 表示构成二分图的左右两个点集中较小的那一个。

其实为什么要设定 $|X|\le|Y|$ 也很简单，如果 $|X| > |Y|$ 的话你在 $|Y|$ 中甚至找不到足够数量的点与 $|X|$ 中的点一一对应。

广义霍尔定理

给定一张二分图。如果存在一个匹配覆盖左部图中的点集 $X$，且存在一个匹配覆盖右部图中的点集 $Y$，那么存在一个匹配同时覆盖 $X$ 和 $Y$。

这个定理其实就是解题的关键。因为点集 $V$ 从点的来源上来讲可以分为左部 $V_l$ 和右部 $V_r$ 两个，并且依据题目的要求匹配 $M$ 要覆盖 $V$，对应的就同时覆盖了点集 $V_l$ 和 $V_r$ 。

以上是对两个定理的基本介绍。接下来我们来基于这两个定理简单推导一下这道题的思路。

首先根据广义霍尔定理，很显然我们如果把二分图分为左部图和右部图，我们只需要单独枚举满足条件的左部图点集和右部图点集然后合并即可。

假设我们已经处理完了满足条件的点集，事实上最终的答案获取就是很简单的双指针：

for(int i = 0; i < r[1].size(); i++) {
    while(j > 0 && r[2][j - 1] + r[1][i] >= t) j--;
    ans += r[2].size() - j;
}

所以现在问题的主要问题是如何快速获取左部图和右部图中满足广义霍尔定理的点集。

那么判断一个点集至少被一个匹配覆盖的方式，我们需要用到霍尔定理。结论如下：

对于一个点集 $S$，如果至少有一个匹配覆盖点集 $S$，则 $S$ 满足：任意非空子集 $T$ 都有 $|T|\le |N(T)|$ 。

其中 $N(T)$ 表示与 $T$ 中节点相邻的点所构成的点集。

其实不难发现，证明这个结论等价于证明霍尔定理，所以这个结论直接认为是对的即可，证明详见附录。

那么有了这个信息，我们可以写出如下代码：

// 秉承着DRY原则，我们把两个雷同的代码写成一个函数
inline void Check(int op) {
    // 在左右部中枚举点集
    for(int s = 0; s <= U; s++) {
        for(int i = 1; i <= n; i++) {
            if(!(s & (1 << (i - 1)))) continue;
            // 找到点集中的点
            w[op][s] += v[op][i]; // 计算点集权值
            c[op][s] |= E[op][i]; // 获得N(S), N()的定义同上
        }
        // 判断 S 本身是否符合 |S|<=|N(S)|
        c[op][s] = (__builtin_popcount(c[op][s]) >= __builtin_popcount(s));
    }
    // 找出 S 的所有子集是否满足 |S|<=|N(S)|
    for(int i = 1; i <= n; i++) {
        for(int s = 0; s <= U; s++) {
            if(!(s & (1 << (i - 1)))) continue;
            c[op][s] = min(c[op][s], c[op][s ^ (1 << (i - 1))]);
        }
    }
}

定理证明

接下来是证明霍尔定理与广义霍尔定理的部分。

霍尔定理证明

霍尔定理

对于一个左部图为 $X$、右部图大小为 $Y$ 的二分图（钦定 $∣X∣≤∣Y∣$），存在边数等于 $∣X∣$ 的匹配的充要条件是：对于左部图的任何一个点集，右部图中和它相邻的点集大小都大于等于它（相邻的点集指的是所有点出边的并集）。

既然是充要条件，我们就分必要和充分两部分来证明。

必要性

其实是显然的，但是以防万一我们还是简单证明一下。证明必要性的话，可以想想条件不成立则结论也不成立。

假设对于一个二分图的左部图来说，有一个子集 $T\subseteq X$ 不满足 $|T|\le |N(T)|$，那么其中至少有一个点找不到对应的匹配，举个例子：

虽然几乎对于左部图 $X$ 所有的子集都满足 $|T|\subseteq|N(T)|$ 但是唯一的例外在左部图中间那一个点上出现了。这就导致即使其他子集都符合条件，有着一个漏洞你就是找不到一个覆盖左部图的匹配。

充分性

充分性的证明其实就是证明如果结论成立，那么条件也一定成立。接下来我们用数学归纳法简单证明一下：

显然当 $|X|=1$ 时，条件成立。
那么接下来我们设对于 $n=|X|$ 所有左部图大小小于 $n$ 的时候条件都成立，接下来就变成如何扩展到 $n$。很显然对于左部图大小 $n-1$ 的二分图来说，根据假设 $N(X)$ 的大小最小为 $n-1$。在满足结论必然至少存在一个覆盖左部图的匹配的条件下，我们至少要往这个二分图中增加一对点，而添加后依然满足 $|X|\le|N(X)|$。
那么充分性的证明就愉快的结束了。

广义霍尔定理证明

霍尔定理证明后，我们来看广义霍尔定理的证明。其实与其说是证明，不如说是找到一个合理的匹配方式。我们给出下面一幅图作为例子：

图例证明

稍加思考（或者你多手玩几组样例），就会发现这个匹配方案必然是正确的。这也变相的证明了这个所谓的“广义霍尔定理”的正确性。

至于这个匹配的正确性，主要问题应该在与为什么处理过后的图只能有偶环和简单链。不难想到由于匹配的定义就是两个点一条边，我们这里合并了两个匹配，所以说一个点最多最多同时被两个匹配占用所以一个点的度数小于等于二，又因为二分图中不存在奇环，所以只能是偶环和简单链。有了这个性质以后，图中所描述的取边方式一定会把每一个点都找到合适的匹配。

完整代码

至此，这道题需要思考的部分完全结束，总体代码如下：

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 20000010;

int n, m, t;
int E[3][30];
int v[3][30];

int U;
int w[3][N];
int c[3][N];
vector<int >r[3];

inline void Input() {
    read(n, m);
    int x;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%1d", &x);
            E[1][i] |= x << (j - 1);
            E[2][j] |= x << (i - 1);
        }
    }
    for(int i = 1; i <= n; i++) {
        read(v[1][i]);
    }
    for(int i = 1; i <= m; i++) {
        read(v[2][i]);
    }
    read(t);
}

inline void Find(int op) {
    for(int s = 0; s <= U; s++) {
        for(int i = 1; i <= n; i++) {
            if(!(s & (1 << (i - 1)))) continue;
            w[op][s] += v[op][i];
            c[op][s] |= E[op][i];
        }
        c[op][s] = (__builtin_popcount(c[op][s]) >= __builtin_popcount(s));
    }
    for(int i = 1; i <= n; i++) {
        for(int s = 0; s <= U; s++) {
            if(!(s & (1 << (i - 1)))) continue;
            c[op][s] = min(c[op][s], c[op][s ^ (1 << (i - 1))]);
        }
    }
}

inline void Work() {
    U = (1 << (n = max(n, m))) - 1;
    Find(1), Find(2);
    for(int s = 0; s <= U; s++) {
        if(c[1][s]) r[1].push_back(w[1][s]);
        if(c[2][s]) r[2].push_back(w[2][s]);
    }
    sort(r[1].begin(), r[1].end());
    sort(r[2].begin(), r[2].end());
    int j = r[2].size();
    ll ans = 0;
    for(int i = 0; i < r[1].size(); i++) {
        while(j > 0 && r[2][j - 1] + r[1][i] >= t) j--;
        ans += r[2].size() - j;
    }
    printf("%lld\n", ans);
}

int main() {
    Input();
    Work();
    return 0;
}