Bipartite Blanket[bzoj4788]

发表于 分类于

题意

给一个 $n+m$ 个点的二分图，求有多少个点集，满足存在至少一个二分图匹配，使得该点集都在这个匹配中，且该点集的权值和大于某个值 $D$。

$n,m\leq 20,D\leq 4\times 10^8$。

题解

假设我们只考虑一边的点的情况。那么由Hall定理，我们就可以暴力判断某个点集是否存在完美匹配。只需要枚举一个子集，这是 $O(3^n)$ 的，显然不行。

不过枚举子集干嘛。。。直接来个高维前缀与和就好了，时间复杂度 $O(n2^n)$。

现在考虑两边点的情况，如果两边的两个点集都满足Hall定理的话，那么一定由一个匹配使得该点集在这个匹配中。只会爆猜结论，并不会证明qwq。。。

那么对两边的点分别做上面的做法，然后按权值和从小到大排序，然后two-pointer扫一遍。

时间复杂度 $O(n2^n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=20;
vector<int> fa,fb;
int a[N],b[N],n,m,T,bit[1<<N];
int va[N],vb[N],h[1<<N];
inline void dp(vector<int> &g,int *val,int *v,int n,int m)
{
    g.clear();
    int f,s;
    ff(i,0,(1<<n))
    {
        f=s=0;
        ff(j,0,n)
            if((1<<j)&i)
                f|=v[j],s+=val[j];
        h[i]=(bit[i]<=bit[f]);
        if(h[i])
            ff(j,0,n)
                if((1<<j)&i)
                    h[i]&=h[i^(1<<j)];
        if(h[i]) g.pb(s);
    }
    sort(all(g));       
}
void init(int n)
{
    ff(i,1,1<<n) ff(j,0,n) bit[i]+=((i>>j)&1);
}
char s[N];
int main()
{
    n=read(); m=read();
    init(max(n,m));
    ff(i,0,n)
    {
        scanf("%s",s);
        ff(j,0,m) if(s[j]=='1') va[i]|=(1<<j),vb[j]|=(1<<i);
    }
    ff(i,0,n) a[i]=read();
    ff(i,0,m) b[i]=read();
    int T=read();
    dp(fa,a,va,n,m);
    dp(fb,b,vb,m,n);
    int i=fb.size()-1,cnt=fb.size()-1;
    ll ans=0;
    for(auto v:fa)
    {
        for(;i>=0&&fb[i]+v>=T;i--);
        ans+=cnt-i;
    }
    cout<<ans;
    return 0;
}