11/10
21:01
OI

[CERC2016]二分毯 Bipartite Blanket [Hall定理][状压]

[CERC2016]二分毯 Bipartite Blanket

首先要知道Hall定理.

二分图点集X,Y,令|X| \leq |Y|,记T(x)为和x相邻点集,如果存在完美匹配,则对于\forall x \subseteq X,有|x| \leq |T(x)|

证明的话,大概就是假设不存在完美匹配,就可以找到增广路这样

然后本题的”覆盖”是指点是匹配端点就行,所以有一个推论:

对于X,Y的子集x,y,如果x,y分别满足Hall定理,那么一定存在一组匹配,使得x,y都在其中.

于是可以分别状压DP求出所有满足的子集,排序双指针扫一扫.

#include <bits/stdc++.h>

const int N = 20, S = (1 << N) + 5;

int n, m, G_A[S], G_B[S], A[N], B[N], T,
  f_A[S], f_B[S], cnt[S];
long long ans;
std::vector<long long> s_A, s_B;
char str[N + 2];

int main() {
  std::cin >> n >> m;

  for (int i = 0; i < n; ++i) {
    std::cin >> str;
    for (int j = 0; j < m; ++j)
      if (str[j] == '1') {
        G_A[1 << i] |= 1 << j;
        G_B[1 << j] |= 1 << i;
      }
  }

  for (int i = 0; i < n; ++i)
    std::cin >> A[i];
  for (int i = 0; i < m; ++i)
    std::cin >> B[i];
  std::cin >> T;

  for (int s = 1; s < 1 << std::max(n, m); ++s)
    cnt[s] = cnt[s >> 1] + (s & 1);

  for (int i = 0; i < n; ++i)
    for (int s = 0; s < 1 << n; ++s)
      if (s & (1 << i))
        G_A[s] |= G_A[s ^ (1 << i)];
  for (int i = 0; i < m; ++i)
    for (int s = 0; s < 1 << m; ++s)
      if (s & (1 << i))
        G_B[s] |= G_B[s ^ (1 << i)];

  for (int s = 0; s < 1 << n; ++s) {
    f_A[s] = 1; long long sum = 0;
    for (int i = 0; i < n; ++i)
      if (s & (1 << i)) {
        f_A[s] &= f_A[s ^ (1 << i)];
        sum += A[i];
      }
    f_A[s] &= cnt[G_A[s]] >= cnt[s];
    if (f_A[s])
      s_A.push_back(sum);
  }
  std::sort(s_A.begin(), s_A.end());

  for (int s = 0; s < 1 << m; ++s) {
    f_B[s] = 1; long long sum = 0;
    for (int i = 0; i < m; ++i)
      if (s & (1 << i)) {
        f_B[s] &= f_B[s ^ (1 << i)];
        sum += B[i];
      }
    f_B[s] &= cnt[G_B[s]] >= cnt[s];
    if (f_B[s])
      s_B.push_back(sum);
  }
  std::sort(s_B.begin(), s_B.end());

  for (int a = 0, b = s_B.size(); a < s_A.size(); ++a) {
    while (b - 1 >= 0 && s_A[a] + s_B[b - 1] >= T)
      --b;
    ans += s_B.size() - b;
  }

  std::cout << ans << std::endl;
  return 0;
}