题解：P3838 [IOI 2017] Toy Train

· · 题解

博弈论好题。

题意

一个 n 点的有向图，每个点至少一个出度，其中一些点是充电站。图上有一辆小火车，一到充电站就会完全满电，满电可以走 n 条边。每个点分给两个人 A,B, 双方对每个点先选择一个边作为出边。火车若能走向一个含有充电站的环则 A 赢。对每个点 u 判定，火车从 u 开始时，无论 B 怎么玩，A 是否必胜。

题解

不希望一次性把所有点的出边全都枚举完。一次性考虑很多东西时，要么可以直接猜出来通性，要么分步考虑。于是我们把游戏转化为序贯的。一种转化思路就是，从起点开始，由火车所在车站的人决定火车往哪里走。这个东西感性上就是把策略展开来成一个搜索树。

但是这样子的博弈状态还是太多了，走上一个有充电器的环的还是太不好判定了。再做一次转化，把第一次进入火车站时就定死出边改成每次进入火车站时都能选择出边。胜利条件改成能无限次走到充电站。

不难发现一个点的状态只有这个点的编号了，于是每次到达一个点必然只会选择一个出边，因为不存在其他任意的信息。于是这等价于在第一次进入时定死出边，自然胜利判断也是等价的。

我们继续改良胜利条件。注意到无限有数学归纳法的等价定义：无论 B 走到哪个点都能再次走到充电站。这个判定还是连终态都得不到的。于是我们正难则反。若一个点无法再次强制到达充电站，那么这个点一定是必败的。假设能到达充电站是必胜，跑一遍有向图博弈（称为第一次有向图博弈），这里的非必胜点一定是原来游戏的必败点。

于是我们可以再跑一遍有向图博弈（称为第二次有向图博弈），现在必败点是确定的。跑出来的非必败点就是答案了吗？交上去发现 WA 了。走到现在这步田地还是因为不严谨导致的。

又感觉博弈论一旦细想就会陷入各种各样的悖论。就举个例子，A,B 哪个先决策会不会有影响？我们可能会想，A 一定能算到 B 在想什么，但是 B 亦然。于是会这样无穷延伸下去。是否会发生这样的延伸是不确定的。比如石头剪刀布就是哪个先决策是重要的。我们先不管这个问题。不要在这里精神内耗，有可能到了后面这些问题才可以得到解答。

下了数据发现，为了不走到必败点，一些平局点是无法到达关键点的。这些点也应该被判掉，这就需要再跑一次上面的流程。如是循环，直到图不发生变化。这样子是 O(n(m+n)) 的。发现是对的。

我们下面严谨地证明以上的每一步。但也请注意，没有上文的尝试、猜想，很难把证明直接搞出来，这就是“先不管证明”的重要性。

我们的思路是先转化为每次进入火车站的时候都做一次决策，A 胜当且仅的那个可以无限次走到充电站。先证明在这个新游戏中，每次走到一个点，必然只会选择同一条路出去。

再次回到一个点时，一定是走了一个环，若这个环没有充电器，说明走过去后对方的最优策略也黔驴技穷，肯定选择之前走的路；若这个环有充电器，而我们换了一条边，说明原来的选择不够优，矛盾。还有一种证明的思路是，显然不会经过无限个点到达充电站（具体地若走了 n 条边都到不了，肯定是走到环上去了，而这个环上没有充电站，又知这是最优策略，那就是必败了），走到一个点时唯一的信息就是自己处于这个点，没有其他的变量与信息自然只会选一种。但是这两个这两个证明都有点危险，因为没有证明是否有纯策略，这个显然是有的，因为可以考虑记录一维上次碰到充电站的时间，这就变成有向图博弈了，而有向图博弈是一定有纯策略的。

对于无限次走到充电站这个朱鹮，因为充电站是有限的，必然存在一个充电站经历了无数次，自然是找到含有充电站的环了。于是这个转化是严谨的。

然后把可以无限次到达充电站转化为：无论 B 走到哪个点都能再次走到充电站。注意走到的充电站也算是无论 B 走到的点，于是这就是数学归纳法，是正确的。直到“跑出来的平局点就是答案”，论述都是比较严谨的。

问题出在所跑的有向图博弈和原问题不等价，不走到必败点不意味着胜利，还有可能是和（对 A 意味着输）。此时确实要离经叛道一下（不是原来的有向图博弈模型了），发现可以增广出来更多的必败点。我们证明增广不出来必败点时，一定是必胜的。增广不出来必败的时候，由于做第一次有向图博弈不对结果产生影响，现在的必胜点必然可以强制到达一个充电站，由于做第二次有向图博弈对结果没有任何影响，这个充电站存在一个后继可以强制到达一个充电站，如是循环往复，可以无限次走到充电站。如果害怕无限的话，到 n+1 个充电站时必然有个充电站到过两次，这是一个有充电站的环。证毕。

思考这道题时，我常常对无穷很担忧，但是这道题中大多数的无穷都可以转化为 n 次或者 n+1 次，这是鸽巢原理带来的方便。

事实上我们不用关心初始化第一次有向图博弈时，本身是充电站算不算，只要本身不是必败点即可。

Code：

#include<bits/stdc++.h>
using namespace std;
//#define int long long//乱开ll见祖宗
#define pbI push_back
#define rep(a,b,c) for(signed a=b;a<=c;a++)
#define MAXN 20010
int n,ans[MAXN],deg[MAXN],lst[MAXN],deg0[MAXN];
bool bel[MAXN],ene[MAXN];
vector<int>vec[MAXN];
vector<int> who_wins(vector<int>a,vector<int>r,vector<int>u,vector<int>v){
    int m=u.size();n=a.size();
    rep(i,0,m-1){vec[v[i]+1].pbI(u[i]+1);deg0[u[i]+1]++;}
    rep(i,0,n-1)bel[i+1]=a[i];rep(i,0,n-1)ene[i+1]=r[i];
    while(1){
        memcpy(lst,ans,sizeof(ans));
        memcpy(deg,deg0,sizeof(deg));
        queue<int>q;
        rep(i,1,n)if(ene[i]&&ans[i]!=-1)q.push(i),ans[i]=1;
        while(q.size()){
            int u=q.front();q.pop();
            for(auto v:vec[u]){
                deg[v]--;if(ans[v])continue;
                if(bel[v]&&(ans[u]==1))ans[v]=1,q.push(v);
                else if(!bel[v]&&(ans[u]==-1))ans[v]=-1,q.push(v);
                else if(!deg[v]){ans[v]=bel[v]?-1:1;q.push(v);}
            }
        }
        memcpy(deg,deg0,sizeof(deg));
        rep(i,1,n)if(ans[i]!=1)ans[i]=-1,q.push(i);
        while(q.size()){
            int u=q.front();q.pop();
            for(auto v:vec[u]){
                deg[v]--;if(ans[v]==-1)continue;
                if(!bel[v]&&(ans[u]==-1))ans[v]=-1,q.push(v);
                else if(bel[v]&&(ans[u]==1))ans[v]=1,q.push(v);
                else if(!deg[v]){ans[v]=bel[v]?-1:1;q.push(v);}
            }
        }
        bool can=0;
        rep(i,1,n)if(lst[i]!=-1&&ans[i]==-1)can=1;
        rep(i,1,n)if(ans[i]!=-1)ans[i]=0;
        if(!can)break;
    }
    vector<int>ret;
    rep(i,1,n)ret.pbI(ans[i]!=-1);
    return ret;
}

这一版代码里面泾渭分明地区分了第一次和第二次有向图博弈。应该不难理解了吧。