自动搬运

查看原文

来自洛谷，原作者为

	伟大的王夫子 hanser忠实粉丝，爱好ACG、古风

搬运于2025-08-24 22:32:47，当前版本为作者最后更新于2022-08-07 21:50:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考察一个点 $(a, b)$，这个点存在的意义就是就是说，如果这一步选了 $x = a$ 这条直线，下一步就可以选 $y = b$，如果没有被选过的话。那么，我们可以建立一张二分图，对于点 $(a, b)$，就相当于是左边的 $a$ 节点向右边 $b$ 节点连一条边。于是，该题被我们转化成了在一张二分图上选点。于是可以得到简化题意：

小 A 与小 B 在一张二分图上选点，小 A 先选，每次选完一个点后，删除该点，并交换选点的人，且下一个人只能选与上一个点右边相连的点。最后选不出来的人输。问小 A 是否必胜。

首先，本题结论为后手必胜当且仅当该二分图存在一个完美匹配。

先证充分性。若该二分图存在一个完美匹配，那么每次只要先手选了一个点，后手就可以选取在完美匹配中与其匹配上的那个点。最后一定是后手选不出来。

再证必要性。即证明若该二分图不存在一个完美匹配，先手就有必胜策略。此时，我们考虑最大匹配。先手可以随意选择一个在最大匹配中不匹配的节点，然后变成后手选点。后手选出的点不可能还在最终方案中仍然不匹配，否则可以将这二点相连，就会形成一个更大的匹配，与该匹配是最大匹配矛盾。然后后手每选一个点，先手显然可以通过同样的方法取得胜利。

#include <bits/stdc++.h>
using namespace std;
const int N = 505, M = 10005;
int n, he[N], vc[M], tot, Ne[M], match[N];
bool vis[N], exist[N << 1];
inline void add(int x, int y) {
	vc[++tot] = y, Ne[tot] = he[x], he[x] = tot;
	exist[x] = exist[y + 500] = 1;
}
bool dfs(int x) {
	for (int i = he[x]; i; i = Ne[i]) {
		int y = vc[i];
		if (!vis[y]) {
			vis[y] = 1;
			if (!match[y] || dfs(match[y])) {
				match[y] = x;
				return 1;
			}
		}
	}
	return 0;
}
int main() {
	scanf("%d", &n);
	for (int i = 1, x, y; i <= n; ++i) {
		scanf("%d%d", &x, &y);
		add(x, y);
	}
	int c1 = 0, c2 = 0;
	for (int i = 1; i <= 500; ++i) c1 += exist[i], c2 += exist[i + 500];
	if (c1 != c2) return puts("Mirko"), 0;
	for (int i = 1; i <= 500; ++i)
		if (exist[i]) {
			memset(vis, 0, sizeof vis);
			if (!dfs(i)) return puts("Mirko"), 0;
		}
	puts("Slavko");
}