P4617 [COCI2017-2018#5] Planinarenje

· · 题解

题意

给定 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;
}

（个人码风奇特）

结语

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