Luogu4232 无意识之外的捉迷藏

题面

简化题意

给定一个 DAG，A,B 两人分别在 $s_a,s_b$ 点。每轮两人同时选择走一步或不动，两人互相知道对方位置，但不知道其下一步行动。B 要尽早地抓到 A，A 要尽晚被 B 抓住，若进行 $t$ 轮后 B 还没抓到 A 则游戏强制截止。求双方都用最优策略时，一局游戏期望要多少轮。

$n,t\leq 20$。

题解

神题，我才不会告诉你我纠结了好久为什么这题有期望。

先把题目信息整理一下：

• “A 尽晚被 B 抓住，B 尽早抓住 A” 说明本题是零和博弈。
• 图是 DAG。
• 数据很小。

DAG 是个好东西，考虑 DP。设 $f_{x,y,k}$ 表示当前 A 在 $x$，B 在 $y$，目前已经过了 $k$ 轮，期望的轮数。随便拿出来一张图：

红色点为 A，蓝色点为 B。

那么对于下一步的决策，有如下表：

A\B	不动	到 $3$	到 $5$	到 $6$
不动	$f_{5,1,t+1}+1$	$f_{5,3,t+1}+1$	$1$	$f_{5,6,t+1}+1$
到 $6$	$f_{6,1,t+1}+1$	$f_{6,3,t+1}+1$	$f_{6,5,t+1}+1$	$1$

发现（当然也显然）它是不会从某一状态节点跳了若干次跳到父亲状态节点，而子问题规模也比原问题小，因此可以记忆搜实现。

双方都是最优策略，说明任意一方改变策略都无法提高自己的收益，双方一直保持自己策略，这恰好是纳什均衡的模型。这个策略可能是与概率/频率相关的，这就是为什么这题有“期望”。

而零和博弈+纳什均衡的策略可以考虑线性规划求解。

具体而言，假设双方策略稳定（最终稳定态）时 B 的得分期望为 $E$，B 的策略为：对于第 $i$ 中决策有 $p_i$ 的概率选择，收益矩阵为 $g$，那么：

$\text{minimize} E$

$\begin{cases} \sum p=1 \\ \forall j,\sum p_i g_{j,i}\leqslant E \end{cases}$

设 $x_i=\frac{p_i}{E}$：

$\text{minimize} \sum x$

$\forall j,\sum x_i g_{j,i}\leqslant1$

然后就可以上线性规划板子了。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=22,max_m=452,inf=1000000009;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
struct graph{
    int ct,hd[max_n],to[max_m],nx[max_m];
    graph(){ct=1;}
    inline void add(int u,int v){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
    }
}e;

// ----------------以下是线性规划板子----------------

struct LinerPro{
    int n,m,id[max_n*2];
    double a[max_n][max_n];
    inline void init(int x,int y){
        n=x,m=y;
        memset(a,0,sizeof(a));
        for(register int i=1;i<=n;++i)
            id[i]=i;
        for(register int i=1;i<=m;++i)
            id[i+n]=0;
    }
    inline void turn(int x,int y){
        swap(id[y],id[x+n]);
        double k=a[x][y];
        a[x][y]=1;
        for(register int i=0;i<=n;++i)
            a[x][i]/=k;
        for(register int i=0;i<=m;++i)
            if(i!=x){
                double k=a[i][y];
                a[i][y]=0;
                for(register int j=0;j<=n;++j)
                    a[i][j]-=a[x][j]*k;
            }
    }
    inline double ask(){
        while(1){
            double k=0;
            int x=0,y=0;
            for(register int i=1;i<=m;++i)
                if(a[i][0]<k)
                    k=a[i][0],x=i;
            if(!x) break;
            for(register int i=1;i<=n;++i)
                if(a[x][i]<0){
                    y=i;
                    break;
                }
            turn(x,y);
        }
        while(1){
            double k=inf;
            int x=0,y=0;
            for(register int i=1;i<=n;++i)
                if(a[0][i]>0){
                    y=i;
                    break;
                }
            if(!y) break;
            for(register int i=1;i<=m;++i)
                if(a[i][y]>0 && a[i][0]/a[i][y]<k)
                    k=a[i][0]/a[i][y],x=i;
            turn(x,y);
        }
        return -a[0][0];
    }
}lp;

// ----------------上面是线性规划板子----------------

int n,m,sr,sk,t,deg[max_n];
double f[max_n][max_n][max_n];

inline double dfs(int u,int x,int p){
    if(f[u][x][p]!=0) return f[u][x][p];
    if(p>t || u==x) return 0;
    for(register int i=e.hd[u];i;i=e.nx[i])
        for(register int j=e.hd[x];j;j=e.nx[j])
            dfs(e.to[i],e.to[j],p+1);
    lp.init(deg[x],deg[u]);
    for(register int i=e.hd[u],c1=1;i;i=e.nx[i],++c1){
        for(register int j=e.hd[x],c2=1;j;j=e.nx[j],++c2)
            lp.a[c1][c2]=f[e.to[i]][e.to[j]][p+1]+1;
        lp.a[c1][0]=1;
    }
    lp.a[0][0]=0;
    for(register int i=1;i<=deg[x];++i)
        lp.a[0][i]=1;
    return f[u][x][p]=1/lp.ask();
}

signed main(){
	n=read(),m=read(),sr=read(),sk=read(),t=read();
	for(register int i=1;i<=m;++i){
	    int u=read(),v=read();
	    e.add(u,v),++deg[u];
	}
	for(register int i=1;i<=n;++i)
	    e.add(i,i),++deg[i];
	printf("%.3lf",dfs(sr,sk,0)); 
	return 0;
}