<h2>题目大意</h2>

二分图点有点权,定义点集的权值为点权和,统计二分图中有多少个点集,满足被至少一个匹配覆盖。
$n,m \leq 20$

<h2>题解</h2>

首先你要知道一个叫做霍尔定理的东西:设 $G$ 中有一组匹配,一端恰好为组成 $X$ 的点的充分必要条件是: $X$ 中的任意 $k$ 个点至少与 $Y$ 中的 $k$ 个点相邻。(摘自百度百科)
这个告诉了我们如何判断一个点集是否能被一个匹配覆盖,但是暴力枚举+模拟时间复杂度不能接受。
所以还有个新科技定理:
如果存在一个匹配覆盖左边的一个点集 $A$, 同时存在一个匹配(不需要和之前的一样)覆盖右边的一个点集$B$。那么就存在一个匹配同时覆盖 $A,B$。
有了这个定理就很好做了。。。这样直接就可以独立处理左右两部分,最后双指针合并了。
现在我们就是要对于一边求出来是否满足霍尔定理中的条件,直接递推一下就好了(如果子集都满足,那么这个点集肯定满足)

/*
 * Author: RainAir
 * Time: 2019-08-25 07:53:58
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = (1<<20)+5;
int l[MAXN],r[MAXN],cnt[MAXN],lv[MAXN],rv[MAXN];
int mp22,t;
bool ll[MAXN],rr[MAXN];
int n,m;
std::vector<int> q1,q2;

signed main(){
    scanf("%lld%lld",&n,&m);
    FOR(i,1,n){
        FOR(j,1,m){
            scanf("%1lld",&mpi);
            if(mpi) l[1<<i-1] |= (1<<j-1),r[1<<j-1] |= (1<<i-1);
        }
    }
    FOR(i,1,n) scanf("%lld",lv+i);
    FOR(i,1,m) scanf("%lld",rv+i);scanf("%lld",&t);
    FOR(i,1,MAXN-1) cnt[i] = cnt[i>>1] + (i&1);
    ll[0] = rr[0] = 1;
    FOR(S,1,(1<<n)-1){
        ll[S] = 1;int sm = 0;
        FOR(i,0,n-1){
            if(S&(1<<i)){
                l[S] |= l[S^(1<<i)];
                ll[S] &= ll[S^(1<<i)];
                if(!ll[S]) break;
                sm += lv[i+1];
            }
        }
        if(!ll[S]) continue;
        if(cnt[S] > cnt[l[S]]) ll[S] = 0;
        else q1.pb(sm);
    }
    FOR(S,1,(1<<m)-1){
        rr[S] = 1;int sm = 0;
        FOR(i,0,m-1){
            if(S&(1<<i)){
                r[S] |= r[S^(1<<i)];
                rr[S] &= rr[S^(1<<i)];
                if(!rr[S]) break;
                sm += rv[i+1];
            }
        }
        if(!rr[S]) continue;
        if(cnt[S] > cnt[r[S]]) rr[S] = 0;
        else q2.pb(sm);
    }
    std::sort(all(q1));std::sort(all(q2));
    int sz1 = q1.size(),sz2 = q2.size();
    q1.insert(q1.begin(),0);
    q2.insert(q2.begin(),0);
    int p1 = 0,p2 = sz2,ans = 0;
    while(p1 <= sz1 && p2 >= 0){
        while(p1 <= sz1 && q1[p1]+q2[p2] < t) p1++;
        ans += (q1.size() - p1);
        p2--;
    }
    printf("%lldn",ans);
    return 0;
}

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏