Codeforces Round 901 (Div. 1)

https://codeforces.com/contest/1874

C. Jellyfish and EVA

题意

给出一张DAG（保证每个点只连向编号比自己大的结点）。有两个人，初始在 $1$ 号结点，希望走到 $n$ 号结点。每次其中一人随机选择一个后继结点，另一个人可以安排自己选择的结点。若两人选择同一个后继结点，则移动到该结点，否则将选择的两个结点都删除。若没有可选的后继结点，就停留在该结点。求另一个人在最优策略下，走到 $n$ 号结点的概率。

$2\leq n\leq 5000,0\leq m\leq \min(\dfrac{n(n-1)}{2},2\times10^5)$。

题解

假如我们知道了点 $u$ 的所有后继结点 $v$ 到 $n$ 的概率 $a_v$，并且假设我们知道了走向第 $i$ 个被选择的结点的概率 $f_i$（可以理解为优先级，即每次都选择在剩余后继结点中优先级最高的），那么一定是让更大的 $f$ 对应更大的 $a$。关于 $f_i$ 的求解可以利用dp，设 $f_{i,j}$ 表示共有 $i$ 个数，优先级第 $j$ 高的数被选择的概率，则

$$f_{i,j}=f_{i-2,j-2}\times\frac{j-1}{i}+f_{i-2,j-1}\times\frac{i-j-1}{i}$$

然后再在dag上做一遍概率dp就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m;
double f[N][N],a[N];
bool vis[N];
vector<int> g[N];
void init()
{
    f[1][1]=1;
    f[2][1]=0.5;
    for(int i=3;i<=n;i++)
    {
        f[i][1]=1.0/i;
        for(int j=2;j<=i;j++) f[i][j]=f[i-2][j-2]*(j-2)/i+f[i-2][j-1]*(i-j)/i;
    }
}
void dfs(int u)
{
    vis[u]=1;
    if(u==n) 
    {
        a[u]=1;
        return;
    }
    vector<double> tmp;
    for(auto v:g[u])
    {
        if(!vis[v]) dfs(v);
        tmp.push_back(a[v]);
    }
    sort(tmp.rbegin(),tmp.rend());
    int k=(int)tmp.size();
    for(int i=0;i<(int)tmp.size();i++) a[u]+=tmp[i]*f[k][i+1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>m;
        init();
        for(int i=1;i<=n;i++) vis[i]=0,a[i]=0,g[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;cin>>u>>v;
            g[u].push_back(v);
        }
        dfs(1);
        cout<<fixed<<setprecision(10)<<a[1]<<'\n';
    }
    return 0;
}