二分图多重匹配

一般的二分图匹配与多重匹配之间的区别就是：

二分图多重匹配：右边的物品可以和多个左边的相匹配，同时右边的物品可以有一个最大匹配容量V[i]

int cnt[maxn],V[maxn];//cnt[i]记录现在第i个星球有多少个人，V[i]记录i星球的容量 
int linker[maxn][15];//linker[i][j]表示第i个星球第j个匹配的人是谁 
bool dfs(int u)
{
    for(int i=1;i<=m;i++)
    {
        if(mapp[u][i]&&!vis[i])//表示第u个人可以匹配第i个星球 
        {
            vis[i]=1;
            if(cnt[i]<V[i])//并且该星球人数未上限，直接匹配 
            {
                linker[i][cnt[i]++]=u;
                return true;
            }
            for(int j=0;j<V[i];j++)
            {
                if(dfs(linker[i][j]))//可以让位置 
                {
                    linker[i][j]=u;
                    return true;
                }
            }
        }
    }
    return false;
}
bool solve()//判断左是否都有匹配一个右,即最大匹配数为n
{
    for(int i=1;i<=n;i++)//查看是否所以人可以逃离 
    {
        mem(vis,false);
        if(!dfs(i))return false;//该人不可以逃离就输出NO
    }
    return true;
}
int count_()//输出多重最大匹配数
{
    mem(linker,-1);
    mem(cnt,0);
    int res=0;
    for (int i=1;i<=n;i++)
    {
        mem(vis,false);
        if (dfs(i))res++;
    }
    return res;
}
           

例题1：HDU3605

https://vjudge.net/problem/HDU-3605

直接给出了左右对应关系，并且给出了右边的容量大小，直接套板子即可，题中所问的是能不能让所有人逃出，所以没必要算最大匹配数(如果算也是可以的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<queue>
#include<map>
#define ll long long
#define pb push_back
#define rep(x,a,b) for (int x=a;x<=b;x++)
#define repp(x,a,b) for (int x=a;x<b;x++)
#define W(x) printf("%d\n",x)
#define WW(x) printf("%lld\n",x)
#define pi 3.14159265358979323846
#define mem(a,x) memset(a,x,sizeof a)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=2e5+7;
const int INF=1e9;
const ll INFF=1e18;
int mapp[maxn][15];
bool vis[maxn];
int linker[maxn][15];
int cnt[maxn],V[maxn],n,m,x;
bool dfs(int u)
{
    for (int i=0;i<m;i++)
    {
        if (mapp[u][i]&&!vis[i])
        {
            vis[i]=true;
            if (cnt[i]<V[i])
            {
                linker[i][cnt[i]++]=u;
                return true;
            }
            for (int j=0;j<V[i];j++)
            {
                if (dfs(linker[i][j]))
                {
                    linker[i][j]=u;
                    return true;
                }
            }
        }
    }
    return false;
}
bool solve()
{
    rep(i,1,n)
    {
        repp(j,0,m)vis[j]=false;
        if (!dfs(i))return false;
    }
    return true;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if (!n&&!m)break;
        repp(i,0,m)cnt[i]=0;
        rep(i,1,n)
        {
            repp(j,0,m)
            {
                scanf("%d",&x);
                if (x==1)mapp[i][j]=1;
                else mapp[i][j]=0;
            }
        }
        repp(i,0,m)scanf("%d",&V[i]);
        if (solve())cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
           

例题2：POJ2289

https://vjudge.net/problem/POJ-2289

左边与右边多重匹配，问右边的最大匹配数的最小值，即假设所有的 V [ i ] , ( 1 ≤ i ≤ m ) V[i],(1\leq i \leq m) V[i],(1≤i≤m)都不超过一个值limit，这个limit就是最终的答案，二分答案limit，找到最小的limit

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<queue>
#include<map>
#define ll long long
#define pb push_back
#define rep(x,a,b) for (int x=a;x<=b;x++)
#define repp(x,a,b) for (int x=a;x<b;x++)
#define W(x) printf("%d\n",x)
#define WW(x) printf("%lld\n",x)
#define pi 3.14159265358979323846
#define mem(a,x) memset(a,x,sizeof a)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=2e3+7;
const int INF=1e9;
const ll INFF=1e18;
int mapp[maxn][maxn],cnt[maxn];
int linker[maxn][maxn];
bool vis[maxn];
int n,m,limit,x;
char s[maxn],ch;
void init()
{
    mem(mapp,0);
}
bool dfs(int u)
{
    for (int i=0;i<m;i++)
    {
        if (mapp[u][i]&&!vis[i])
        {
            vis[i]=true;
            if (cnt[i]<limit)
            {
                linker[i][cnt[i]++]=u;
                return true;
            }
            for (int j=0;j<cnt[i];j++)
            {
                if (dfs(linker[i][j]))
                {
                    linker[i][j]=u;
                    return true;
                }
            }
        }
    }
    return false;
}
bool count_()
{
    mem(cnt,0);
    for (int u=1;u<=n;u++)
    {
        mem(vis,false);
        if (!dfs(u))return false;
    }
    return true;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if (!n&&!m)break;
        init();
        rep(i,1,n)
        {
            scanf("%s",s);
            while(1)
            {
                scanf("%d%c",&x,&ch);
                mapp[i][x]=1;
                if (ch=='\n')break;
            }
        }
        int l=0,r=n;
        while(l<r)
        {
            limit=(l+r)/2;
            if (count_())r=limit;
            else l=limit+1;
        }
        W(r);
    }
    return 0;
}