自动搬运

查看原文

来自洛谷，原作者为

	zac2010 a vegedog

搬运于2025-08-24 21:51:32，当前版本为作者最后更新于2023-08-13 18:28:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑霍尔定理和广义霍尔定理：

霍尔定理：对于一个左部图为 $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$。发现这样的图中只存在独立的环或者独立的链，于是我们对两种情况分类讨论一下：

  1. 对于一个环

     由于当前二分图只有偶环，故而考虑隔一条边取一次。

  2. 对于一条链

     如果当前是奇链，那就从一端开始隔一条边取一次。

     如果当前是偶链，会发现 $X\cup Y$ 不等于两个匹配并集的总点数（注意到 $X,Y$ 与匹配中的点是有区别的，匹配中的点包含了左部点和右部点，而 $X,Y$ 都只是“左部点和右部点”中的一种），于是我们规避掉实际上不处于 $X\cup Y$ 的点就行了。

根据广义霍尔定理，我们对于点集 $A$ 与点集 $B$ 单独考虑合法性，然后再合并方案即可。

• 判定点集 $S$ 的合法性

  判断权值是否不小于 $t$ 好做，枚举每个点判断是否在集合里，求和再与 $t$ 比较即可。

  判断一个点集是否被至少一个匹配包含，可以依据霍尔定理（要满足下面所述的两个条件）：

  1. $|S|$ 不大于 $S$ 的相邻节点集合
  2. $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;
}