题目链接：Codeforces 1139E

在一所学校中有 $n$ 个学生和 $m$ 个俱乐部。俱乐部从 $1$ 到 $m$ 标号。每个学生拥有一个潜力值 $p_i$，且属于第 $c_i$ 个俱乐部。

刚开始每个学生都恰好属于一个俱乐部，后来学校举办了一次技能测试，这场测试持续了 $d$ 天。每天上午都会有恰好一个学生离开他的俱乐部。一个学生一旦离开就不会再次加入任何一个俱乐部。每天下午，每个俱乐部需要选出一个人，以此组成一个 $m$ 个人的队伍来参加比赛。一支队伍的能力为队员潜力值的 $\text{mex}$（即最小的未出现过的非负整数）。学校想知道每一天能组成的队伍的能力最大值。

数据范围：$1\le m \le n \le 5000$，$0 \le p_i < 5000$，$1 \le c_i \le m$，$1 \le d \le n$。

Solution

我们发现这个问题可以转化为匹配问题。即为每个潜力值匹配一个人，一个人匹配一个潜力值。如果我们直接删边比较困难，不妨考虑将删除离线下来倒着进行，这样就转化为加边。

建立一张二分图，左部为潜力值，右部为学生。一个潜力值和一个学生之间有边当且仅当这个学生拥有这个潜力值。

注意到转化后答案一定是递增的。假设当前答案为 $x​$，我们尝试将潜力值为 $x + 1​$ 的点向右部匹配，如果能够匹配则继续匹配 $x + 2​$ 直到无法匹配。

这个二分图匹配问题可以直接使用匈牙利算法实现。

时间复杂度：$\mathcal O(dn + mn)$。

Code

#include <cstdio>

const int N = 1e4 + 5;

int n, m, q, p[N], c[N], k[N], vis[N], mat[N], ans[N];
int tot, lnk[N], ter[N], nxt[N];
bool del[N];

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
bool dfs(int u, int tag) {
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (vis[v] == tag) continue;
        vis[v] = tag;
        if (!mat[v] || dfs(mat[v], tag)) {
            mat[v] = u;
            return true;
        }
    }
    return false;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) scanf("%d", &k[i]), del[k[i]] = true;
    for (int i = 1; i <= n; i++) {
        if (!del[i]) {
            add(n + p[i] + 1, c[i]);
            add(c[i], n + p[i] + 1);
        }
    }
    int mex = 0, tag = 0;
    for (int i = q; i >= 1; i--) {
        for (; dfs(n + mex + 1, ++tag); mex++);
        ans[i] = mex;
        add(n + p[k[i]] + 1, c[k[i]]);
        add(c[k[i]], n + p[k[i]] + 1);
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0;
}