自动搬运

查看原文

来自洛谷，原作者为

	Sunny郭 缺失边界感之人

搬运于2025-08-24 22:02:00，当前版本为作者最后更新于2023-01-11 19:23:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

给定 $n$ 代表 $n$ 个山峰和山谷，给定 $m$ 代表 $m$ 条道路，给定 $m$ 条道路，第 $i$ 个山峰出发 Mirko 赢的条件：从山峰 $i$ 开始走，每次“山谷——山峰——山谷……”依次选，如果最后是山峰，就赢。

算法分析

由题目可知，山峰和山峰之间没有路，山谷同理，于是把山峰和山谷各自划分为一个集合的话，可以发现这是个“二分图”。

最优策略几个字容易想到是“博弈”。

再从本质出发，每次都会在两个状态（选山峰或者山谷）之间交替，所以这题是“二分图博弈”。

算法讲解

二分图博弈可以使用匈牙利算法（求最大匹配）解决。

本题目的先手：斯拉夫科( Slavko ) ——游戏开局先选山谷。

猜想：

如果最大匹配一定包含 $S1$（一个点），那么先手只需要一直按照匹配选点即可，所以先手必胜。

证明：

定义：非匹配点为少了这个点也可以完成最大匹配的点。

后手不可能选到非匹配点，如果后手选到一个非匹配点，设路径为 $S_{1} \sim S_{n}$，那么把现在的匹配 $S_{1} \sim S_{n}$ 换成 $S_{2} \sim S_{n}$，匹配数不变但不包含 $S_{1}$，与最大匹配一定包含 $S_{1}$ 矛盾。（补充讲解）

结论：

当一个点在所有最大匹配的方案中（少了这个点无法最大匹配），那么先手必胜。

算法实现

先跑一遍最大匹配（我这里使用匈牙利），再从每个非最大匹配点开始使用 dfs 搜路径，并把途经的的点都标记为先手输（搜路径的通俗理解：把非匹配点与相邻的点匹配，此时最大匹配数不变，那么本来与此相邻点匹配的点是非匹配点）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int i, j, k, n, m, l, a, b;
int h[N], p[N], v[N], ans[N];
struct ab{
	int b, n;
}d[N];
inline void cun(int a, int b){
	d[++l].b=b, d[l].n=h[a], h[a]=l;
}
int dfs(int a){
	for(int i=h[a]; i; i=d[i].n){
		int b=d[i].b;
		if(v[b]!=k&&(v[b]=k))//使用k（全局变量）来充当时间戳，避免memset耗时太多
			if(!p[b]||dfs(p[b])) return p[b]=a;//模板
	}
	return 0;
}
void sec(int a){
	ans[a]=1;//是非最大匹配中的点
	for(int i=h[a]; i; i=d[i].n){
		int b=d[i].b;
		if(~v[b]) v[b]=-1, sec(p[b]);//“~”可以判断是否-1，是-1会返回0，此处赋值为-1的原因是，避免数组初始时为0的误判
        	//找非匹配点找山峰的即可（山峰出发），所以是sec(p[b])，而不是sec(b)
	}
}
signed main(){
	scanf("%d%d", &n, &m);
	for(i=1; i<=m; ++i){
		scanf("%d%d", &a, &b);
		cun(a, b);//匈牙利算法，a和b存有向边即可
	}
	for(k=1; k<=n; ++k) if(!dfs(k)) sec(k);
   	//dfs(k)==1代表是在当前这个最大匹配中，不为1时，就要深搜找路喽~
	for(k=1; k<=n; ++k) puts(ans[k]?"Mirko":"Slavko");
	return 0;
}

（个人码风奇特）

结语

相当于是模板题？如果事先不知道此做法的话会有一点难度。