「算法笔记」二分图多重匹配

发表于 | | 阅读次数:
字数统计: 888 字
在二分图最大匹配问题中，每个点最多只能和一条匹配边相关联。但是二分图多重匹配中，每个点可以多次匹配但是有匹配上限。

例题

Description

学校运动会即将开始，运动会有 $m$ 个项目，第 $i$ 个项目每个班必须派出 $p_i$ 名学生参加。班级里有 $n$ 名学生，第 $i$ 名学生最多参加 $a_i$ 个项目，并且他给出了他擅长的 $b_i​$ 个项目的编号。求是否有一个合适的安排满足条件。

数据范围：$1\le n,m\le 100$

Solution

我们把 $n$ 名学生和 $m$ 个项目看作是二分图的 $A,B$ 两部。那么每个学生向他擅长的项目连边。这就是二分图匹配的一般思想。

由于有 $a_i$ 和 $p_i$ 的限制，我们要求 $A$ 部的点关联的边不能超过 $a_i$ 个，那么我们需要一个方法来限制这个量在 $[0,a_i]$ 之间。这样一来，有没有感觉特别想网络流中的容量？

于是我们可以对二分图进行扩展，建立源点 $s$ 和汇点 $t$，在 $s$ 和 $A$ 部的第 $i$ 个点之间连一条容量为 $a_i$ 的边，在 $A$ 部和 $B$ 部之间相连的边的容量为 $1$，从 $B$ 部的第 $i$ 个点向 $t$ 连一条容量为 $p_i$ 的边。这个连边方式的正确性显然。

我们对这张图跑最大流，然后分析一下各个边的含义：

  • 边 $(s,A_i)$ 表示学生 $A_i$ 参加的项目数量。
  • 边 $(A_i,B_j)$ 表示 $A_i$ 是否参加了 $B_j$ 项目。
  • 边 $(B_i,t)$ 表示项目 $B_i$ 的参加人数。

所以是否有合适方案，我们只要判断是否所有的边 $(B_i,t)$ 都满流即可！

时间复杂度：$O((n+m)\cdot(nm)^2)$（$\text{Dinic}$）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=205,M=5e4+5;
int n,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

int id(int p,int x) {
    return p==1?x:n+x;
}
void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
    add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
    memset(dep,0,sizeof(dep));
    memcpy(cnr,lnk,sizeof(lnk));
    std::queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
        }
    }
    return dep[t];
}
int dfs(int u,int t,int flow) {
    if(u==t) return flow;
    int ans=0;
    for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
        cnr[u]=i;
        int v=ter[i];
        if(val[i]&&dep[v]==dep[u]+1) {
            int x=dfs(v,t,std::min(val[i],flow-ans));
            if(x) val[i]-=x,val[i^1]+=x,ans+=x;
        }
    }
    if(ans<flow) dep[u]=-1;
    return ans;
}
void dinic(int s,int t) {
    while(bfs(s,t)) while(dfs(s,t,1<<30));
}
int main() {
    scanf("%d%d",&n,&m);
    int S=0,T=n+m+1;
    for(int i=1;i<=m;++i) {
        int x;
        scanf("%d",&x);
        addedge(id(2,i),T,x);
    }
    for(int i=1;i<=n;++i) {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(S,id(1,i),x);
        while(y--) {
            int j;
            scanf("%d",&j);
            addedge(id(1,i),id(2,j),1);
        }
    }
    dinic(S,T);
    bool flg=1;
    for(int i=lnk[T];i;i=nxt[i]) flg&=!val[i^1];
    puts(flg?"Yes":"No");
    return 0;
}

习题

0%