【0】题解：P7753 [COCI 2013/2014 #2] LINIJE

ExFish · 2025-11-20 21:14:24 · 题解

你就发现一个点要是选了行就只能选同列其他点。显然这个关系可以把 x,y 轴当做二分图两点连边 x\to y 然后染色就做完了。结论为后手必胜当且仅当该二分图存在一个完美匹配。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n;
bool bx[N],by[N];
vector<int>e[N];
int npy[N];
bool found[N];
bool dfs(int p){
    for(auto v:e[p])if(!found[v]){
        found[v]=1;
        if(!npy[v]||dfs(npy[v])){
            npy[v]=p;
            return 1;
        }
    }
    return 0;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        bx[x]=1,by[y]=1;
    }
    int cx=0,cy=0;
    for(int i=1;i<=500;i++)
        cx+=bx[i], cy+=by[i];
    if(cx!=cy)
        return cout<<"Mirko",0;
    for(int i=1;i<=500;i++)if(bx[i]){
        memset(found,0,sizeof(found));
        if(!dfs(i)) return cout<<"Mirko",0;
    }
    cout<<"Slavko";
    return 0;
}