Maximize Mex

题面

在一所学校里有 $n$ 名学生和 $m$ 个社团，社团被编号为 $1$ ~ $m$ 。第 $i$ 个学生有一个能力值 $p_i$ ，且属于社团 $c_i$ （每个学生恰好属于一个社团） 。

学校将要举行一个为期 $d$ 天的活动，每天学校要举行一场程序设计比赛 —— 校长将会从每个社团中各选出一个人（如果某个社团没有人，就不选）组成一个队，令队里的学生的能力值的集合为 $S$ ，则该队的总能力值为 $mex(S)$ 。

$mex(S)$ 表示 $S$ 中没有出现的最小的非负整数。例如：

$mex(\{0,1,3,4\})=2;mex(\{1,2,3\})=0$

但是由于学业繁忙，第 $i$ 天时，第 $k_i$ 个学生会离开社团（在校长选这一天参加比赛的学生之前）。

校长希望知道对于活动的每一天，他可能选出的队伍的总能力值最大是多少。

题解

二分图模型维护 mex。

代码

const int N = 5010;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int a[N], b[N], c[N];
	bool used[N];
	int p[N], ans[N];
	int head[N], tot;
	struct Edge {int to, nxt;} e[N];
	void add_edge(int u, int v) { e[++tot] = (Edge) {v, head[u]}, head[u] = tot;}
	bool find(int u) {
		if (used[u]) return 0;
		used[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) 
			if (p[e[i].to] == -1 || find(p[e[i].to])) {
				p[e[i].to] = u; return 1;
			}
		return 0;
	}
	int main () {
		memset (p, -1, sizeof p);
		n = Read(), m = Read();
		for (int i = 1; i <= n; i++) a[i] = Read();
		for (int i = 1; i <= n; i++) b[i] = Read();
		m = Read();
		for (int i = 1; i <= m; i++) used[c[i] = Read()] = 1;
		for (int i = 1; i <= n; i++) if (!used[i]) add_edge(a[i], b[i]);
		int mex = 0;
		for (int i = m; i; --i) {
			memset (used, 0, sizeof used);
			for (; find(mex); mex++, memset (used, 0, sizeof used));
			add_edge(a[c[i]], b[c[i]]); ans[i] = mex;
		}
		for (int i = 1; i <= m; i++) printf ("%d\n", ans[i]);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}