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

在二分图最大匹配问题中,每个点最多只能和一条匹配边相关联。但是二分图多重匹配中,每个点可以多次匹配但是有匹配上限。


例题

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)$ 都满流即可!

时间复杂度:$\mathcal O((n+m)\cdot(nm)^2)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 205, M = 5e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[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(cur, 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 = cur[u]; i && ans < flow; i = nxt[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, INF));
}
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);
        for (int k = 1; k <= y; k++) {
            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;
}

习题

发表评论