• 一道感觉挺模板的题目：Maximize Mex

代码

#include <bits/stdc++.h>
#define N 20005
using namespace std;
int n, m, d, p[N], k[N], c[N], ans[N], dfn;
int match[N], vis[N];
vector<int> g[N];

inline void read(int &x) {
	char ch = x = 0;
	int m = 1;
	while (!isdigit(ch)) {
		if (ch == '-') m *= -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = (x << 1) + (x << 3) + ch - 48;
		ch = getchar();
	}
	x *= m;
	return ;
}

inline void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	static int stk[50];
	int top = 0;
	do {
		stk[++top] = x % 10;
		x /= 10;
	} while (x);
	while (top) {
		putchar(stk[top--] + 48);
	}
	putchar('\n');
	return ;
}

bool dfs(int u) {
	vis[u] = dfn;
	for (int v : g[u]) {
		if (match[v] == -1) {
			match[v] = u;
			return 1;
		}
	}
	for (int v : g[u]) {
		if (vis[match[v]] != dfn && dfs(match[v])) {
			match[v] = u;
			return 1;
		}
	}
	return 0;
}

int main() {
	read(n), read(m);
	for (int i = 1; i <= n; i++) read(p[i]);
	for (int i = 1; i <= n; i++) read(c[i]);
	read(d);
	for (int i = 1; i <= d; i++) {
		read(k[i]);
		vis[k[i]] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i] && p[i] <= m) {
			g[p[i]].push_back(c[i] + m);
			g[c[i] + m].push_back(p[i]);
		}
	}
	memset(match, -1, sizeof match);
	memset(vis, 0, sizeof vis);
	for (int i = d; i; i--) {
      //dfn++; 为什么不能放在这里
		for (int j = ans[i + 1]; j <= m; j++) {
			dfn++; //就是这里
			if (!dfs(j)) {
				ans[i] = j;
				break;
			}
		}
		if (p[k[i]] > m) continue;
		g[p[k[i]]].push_back(c[k[i]] + m);
		g[c[k[i]] + m].push_back(p[k[i]]);
	}
	for (int i = 1; i <= d; i++) print(ans[i]);
	return 0;
}

• 代码最后一个循环就是求解答案，那个 dfn++ 就相当于 memset(vis, 0, sizeof vis)。
• 请问为什么这个 dfn++ 要放在内层循环而不是外层循环呢？我个人认为不应该是每次匹配都要用同样的 vis 来保证不会重复选择同一个社团，所以应该放在外层循环呀？（放在外层循环时几乎没有 WA，说明放外面问题不大，很少出锅）有大佬能讲讲嘛？