Prutekoi's blog

这个定理是用来解决二分图子集最大匹配的。

完备匹配的定义为最大匹配为 $min(n,m)$。

设左部点点数为 $n$，右部点点数为 $m$，且 $n\leq m$。则存在完备匹配当且仅当对于左部点任意一个子集 $W$ 都有 $|N(W)|\geq |W|$。其中 $N(W)$ 为与 $W$ 相连的点集。

推论:二分图最大匹配数为 $n-max\{|W|-|N(W)|\}$。当然跟 $n$ 取 $min$。

看起来这个定理好像完全不能用，因为太暴力了。。枚举所有子集啊。。还不如直接跑匈牙利或者流。

不过有一类题需要对点集的每一个子集判断是否存在完备匹配或求最大匹配。那么这时我们按集合大小从小到达解决，可以利用之前求解过的状态，于是复杂度就变成了 $O(n2^n)$。相当于线性求最大匹配了哦。具体看代码吧。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=30,M=2e6;
int n,m,a1[N],a2[N],v1[N],v2[N],fl[M],num1[M],num2[M],t1,t2,T;char s[N];LL ans;
void solve(){//这个问题需要求解左部点所有子集跟右部点是否能构成完备匹配。直接hall定理即可。
    int mx=1<<n;
    for(int i=0;i<mx;i++){
        int to=0,n1=0,n2=0,vl=0;fl[i]=1;
        for(int j=0;j<n;j++)if(i>>j&1)
            fl[i]&=fl[i^1<<j],to|=a1[j],n1++,vl+=v1[j];
        for(int j=0;j<m;j++)if(to>>j&1)n2++;
        if(n1>n2)fl[i]=0;//这部分是hall定理判定完备匹配。
        if(fl[i])num1[++t1]=vl;
    }
    sort(num1+1,num1+t1+1);
}
int main(){//hardoj 1346
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",s);
        for(int j=0;j<m;j++)if(s[j]^48)
            a1[i]|=1<<j,a2[j]|=1<<i;
    }
    for(int i=0;i<n;i++)scanf("%d",&v1[i]);
    for(int i=0;i<m;i++)scanf("%d",&v2[i]);
    scanf("%d",&T);solve();
    swap(a1,a2);swap(v1,v2);swap(n,m);swap(num1,num2);swap(t1,t2);
    solve();
    for(int i=1,j=t2+1;i<=t1;i++){
        while(j>1&&num1[i]+num2[j-1]>=T)j--;
        ans+=t2-j+1;
    }
    printf("%lld\n",ans);
    return 0;
}