P7753 [COCI2013-2014#2] LINIJE 题解

伟大的王夫子 · 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");
}