题目大意

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

题解

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

/*
 * Author: RainAir
 * Time: 2019-08-25 07:53:58
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#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 mp[22][22],t;
bool ll[MAXN],rr[MAXN];
int n,m;
std::vector q1,q2;

signed main(){
    scanf("%lld%lld",&n,&m);
    FOR(i,1,n){
        FOR(j,1,m){
            scanf("%1lld",&mp[i][j]);
            if(mp[i][j]) l[1<>1] + (i&1);
    ll[0] = rr[0] = 1;
    FOR(S,1,(1< cnt[l[S]]) ll[S] = 0;
        else q1.pb(sm);
    }
    FOR(S,1,(1< 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("%lld\n",ans);
    return 0;
}


版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/784/

转载时须注明出处及本声明

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