关于匹配的一些图论定理

· · 个人记录

二分图匹配：

定义二分图G的两部点集分别为X,Y

完美匹配：二分图中|X|=|Y|，大小为|X|的匹配，即最大匹配为所有点的匹配。

二分图存在完美匹配的充要条件（霍尔定理）：

设集合R(U)表示点集U的出边能到达的Y中的点的集合。

如果二分图G存在完美匹配，当且仅当\forall U\subseteq X,|U|\le|R(U)|。

证明：先咕着。

根据霍尔定理可以得到一个比较重要的推论：

二分图的最大匹配数就等于

|X|-\max_{U\subseteq X}\{|U|-|R(U)|\}

(这里好像得要求去掉X中没有连边的点)

简单证明一下：

对于某一个子集U，即使这个子集里面的点全部和另一侧的点形成匹配，也会有|U|-|R(U)|个点不会形成匹配，所以匹配数一定不会超过上式的值。

接下来证明匹配数一定会达到这个上界，我们找到|U|-|R(U)|最大的那一个子集，我们假想有另外一张图G'，这张图在图G的基础上，在Y部加上|U|-|R(U)|个点形成，这些新加上的点与X中的每一个点都连边。 我们发现这个新图中，所有集合的|R(U)|-|U|\ge 0。也就是说这个新图存在完美匹配，也就是说新加入的这些点每个点都在匹配中，共有|R(U)|-|U|个，那么剩下的其他点就会有达到上式的最大匹配。证毕。

并且霍尔定理也有在一般图的匹配上有推广。设一般图G(V,E)

一般图存在完美匹配当且仅当

\forall U\subseteq V,oc(G_{V\backslash U})\le |U|

其中G_{V\backslash U}表示将点集U以及所有U的连边删去后的图，oc(G)表示图G的奇联通分量的个数。

并且还有一般图的最大匹配等于：

|V|-\max_{U\subseteq V}\{oc(G_{V\backslash U})-|U|\}

证明和二分图的类似。

习题：ARC076 Exhausted?

题意：二分图左边有n个点，右边有m个点，左边的每个点i会向右边的[1,l_i]\cup[r_i,m]中的点连边，求最大匹配。

那么求最大匹配就是求

n-\max_{U\subseteq n}\{|U|-|R(U)|\}

注意到其中R(U)一定是一个前缀和一个后缀的并，那么我们直接用线段树求一下就好了。（你问我为什么不说详细一些，因为实在是太懒了以及这个题并不难，实在不会的话看一下其他人博客吧qwq）。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 210000
#define ls i<<1
#define rs i<<1|1
int maxm[N<<2],tag[N<<2];
struct ques{
    int l,r,d;
    bool operator < (const ques &B) const {return r<B.r;}
}md[N<<2];
void build(int i,int l,int r)
{
    if (l==r) {maxm[i]=1-l;return;}
    int mid=l+r>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    maxm[i]=max(maxm[ls],maxm[rs]);
}
void pushdown(int i,int l,int r)
{
    if (tag[i])
    {
        int mid=l+r>>1,&x=tag[i];
        maxm[ls]+=x;tag[ls]+=x;
        maxm[rs]+=x;tag[rs]+=x;
        x=0;
    }
}
void update(int i,int l,int r,int L,int R,int d)
{
    if (L<=l&&r<=R)
    {
        maxm[i]+=d;
        tag[i]+=d;
        return;
    }
    int mid=l+r>>1;
    pushdown(i,l,r);
    if (L<=mid) update(ls,l,mid,L,R,d);
    if (mid<R) update(rs,mid+1,r,L,R,d);
    maxm[i]=max(maxm[ls],maxm[rs]);
}
int query(int i,int l,int r,int L,int R)
{
    if (L<=l&&r<=R) return maxm[i];
    pushdown(i,l,r);
    int mid=l+r>>1;
    if (R<=mid) return query(ls,l,mid,L,R);
    else if (L>mid) return query(rs,mid+1,r,L,R);
    return max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
inline int read(){
    int n=0;char a;bool z=false;
    while(a=getchar())
    {
        if (a>'9'||a<'0')
            if (z) break;
            else continue;
        if (!z) z=true;
        n=(n<<3)+(n<<1)+(a^48);
    }
    return n;
}
int main()
{
    int n=read(),m=read(),c=0,l,r,ans=max(n,m);
    for (int i=1;i<=n;++i)
    {
        l=read()+1;r=read()-1;
        if (l>r) continue;
        md[++c]=(ques){r,l,1};
        md[++c]=(ques){l,r+1,-1};
    }
    sort(md+1,md+1+c);build(1,1,m);
    for (int i=1,j=1;i<=m;++i)
    {
        while(j<=c&&md[j].r==i)
        {
            l=md[j].l;r=md[j].r;
            if (l>r) swap(l,r);
            update(1,1,m,l,r,md[j].d);
            ++j;
        }
        ans=max(ans,i+maxm[1]);
    }
    printf("%d",ans-m);
    return 0;
}

//by qlwpc

CF1009G Allowed Letters

题意：给你一个字符集大小为6的字符串，你现在要把这个字符串重排成一个字典序最小的字符串，有些位置上限制只能填某些字母的子集，无解输出Impossible。|s|\le 10^5

直接每次贪心最小的填可能就填不完整个串了，那么问题转化成你想象有一个二分图，一边是六个字母，另一边是m个位置，每个位置向能填上的字母连边，问题就是求一个字典序最小的完美匹配。

那么我们一位一位的考虑，每一位上填一个字母后要check一下现在的后面还有没有完美匹配。

方法一：相当于找哪些边不一定在最大匹配上，可以用网络流增广来做。

方法二：由于字符集很小，我们就能枚举字符集的子集直接用霍尔定理来判断是否合法。这里我代码采用了方法二。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 110000
#define ll long long
char s[N],ans[N];int rs[70],G[N][64],E[N];
inline int read(){
    int n=0;char a;bool z=false;
    while(a=getchar())
    {
        if (a>'9'||a<'0')
            if (z) break;
            else continue;
        if (!z) z=true;
        n=(n<<1)+(n<<3)+(a^48);
    }
    return n;
}
int main()
{
    scanf("%s",s+1);
    int m=strlen(s+1),n=read(),len,x;
    for (int i=1;i<=m;++i) ++rs[1<<s[i]-'a'];
    for (int S=0;S<64;++S) if (S&S-1) rs[S]=rs[S&S-1]+rs[S&-S];
    for (int i=1;i<=n;++i)
    {
        x=read();scanf("%s",s+1);
        len=strlen(s+1);
        for (int j=1;j<=len;++j) E[x]|=1<<s[j]-'a';
    }
    for (int i=1;i<=m;++i) if (!E[i]) E[i]=63;
    for (int i=m;i;--i)
        for (int S=0;S<64;++S)
            G[i][S]=G[i+1][S]+(S&E[i]?1:0);
    for (int i=1;i<=m;++i)
    {
        bool zz=false;
        for (int j=1;j<=6;++j)
        {
            if (!rs[1<<j-1]||!(E[i]&1<<j-1)) continue;
            bool Z=true;
            for (int S=0;S<64;++S)
                if (G[i+1][S]<rs[S]-(S&1<<j-1?1:0)) {Z=false;break;}
            if (Z)
            {
                ans[i]=j+'a'-1;
                zz=true;
                for (int S=0;S<64;++S) rs[S]-=S&1<<j-1?1:0;
                break;
            }
        }
        if (!zz) return !printf("Impossible");
    }
    printf("%s",ans+1);
    return 0;
}

//by qlwpc

bzoj5404 Party

题意解释不清楚…，题目要求c个人要在他们的LCA处相聚，那么我们要求出每个人到LCA能拿到哪些特产。这个东西用树剖加bitset维护以下，并且如果每个点在维护一个bitset表示从链头到当前点的这个前缀中的特产集合，这样查询的复杂度是O(NlogN\cdot \frac M{32})的。

接下来询问这五个人最多能拿到多少特产，这其实也是一个二分图匹配，并且求的是类似一个"平均匹配"的东西，求法就是2^c枚举子集，答案就是min\{\frac {C(U)}{|U|}\}，U为枚举的集合，C(U)表示U这个集合所能选的特产数。

#include<cstdio>
#include<bitset>
#include<iostream>
using namespace std;
#define N 300020
#define M 1005
#define ls i<<1
#define rs i<<1|1
struct node{
    int to,next;
}q[N<<1];
int head[N],ss,a[N],son[N],top[N],sz[N],fa[N],dep[N],dfn[N],tm,idt[N],h[10],n,cnt[M];
bitset<M> S[N<<2],E[50],tp,SS,pr[N];
void addedge(int x,int y) {q[++ss]=(node){y,head[x]};head[x]=ss;}
void dfs1(int i)
{
    sz[i]=1;dep[i]=dep[fa[i]]+1;
    for (int j=head[i];j;j=q[j].next)
    {
        int t=q[j].to;
        fa[t]=i;
        dfs1(t);
        sz[i]+=sz[t];
        if (sz[t]>sz[son[i]]) son[i]=t;
    }
}
void dfs2(int i,int T)
{
    dfn[i]=++tm;
    idt[tm]=i;
    top[i]=T;
    pr[i].set(a[i]);
    if (i^T) pr[i]|=pr[fa[i]];
    if (son[i]) dfs2(son[i],T);
    for (int j=head[i];j;j=q[j].next)
        if (!dfn[q[j].to])
            dfs2(q[j].to,q[j].to);
}
void build(int i,int l,int r)
{
    if (l==r)
    {
        S[i].set(a[idt[l]]);
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    S[i]=S[ls]|S[rs];
}
bitset<M> query(int i,int l,int r,int L,int R)
{
    if (L<=l&&r<=R) return S[i];
    int mid=l+r>>1;
    if (R<=mid) return query(ls,l,mid,L,R);
    else if (L>mid) return query(rs,mid+1,r,L,R);
    return query(ls,l,mid,L,R)|query(rs,mid+1,r,L,R);
}
int LCA(int x,int y)
{
    while(top[x]^top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
bitset<M> Query(int x,int y)
{
    tp.reset();
    while(top[x]^top[y])
    {
        tp|=pr[x];
        x=fa[top[x]];
    }
    tp|=query(1,1,n,dfn[y],dfn[x]);
    return tp;
}
inline int read(){
    int n=0;char a;bool z=false;
    while(a=getchar())
    {
        if (a>'9'||a<'0')
            if (z) break;
            else continue;
        if (!z) z=true;
        n=(n<<1)+(n<<3)+(a^48);
    }
    return n;
}
int main()
{
    n=read();int m=read(),Q=read(),c,lca,nn,ans;
    for (int i=2;i<=n;++i) addedge(read(),i);
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=100;++i) cnt[i]=cnt[i>>1]+(i&1);
    dfs1(1);dfs2(1,1);build(1,1,n);
    while(Q--)
    {
        c=read();nn=1<<c;ans=m;
        for (int i=1;i<=c;++i) h[i]=read();
        lca=h[1];
        for (int i=2;i<=c;++i) lca=LCA(lca,h[i]);
        for (int i=1;i<=c;++i) E[1<<i-1]=Query(h[i],lca);
        for (int sta=1;sta<nn;++sta)
        {
            if (sta&sta-1) E[sta]=E[sta&sta-1]|E[sta&-sta];
            ans=min(ans,(int)E[sta].count()/cnt[sta]);
        }
        printf("%d\n",ans*c);
    }
    return 0;
}

//by qlwpc