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

你就发现一个点要是选了行就只能选同列其他点。显然这个关系可以把

x,y

轴当做二分图两点连边

x\to y

然后染色就做完了。结论为后手必胜当且仅当该二分图存在一个完美匹配。

CPP

#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;
}

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

文章操作

相关推荐

评论

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