题解：AT_arc016_4 [ARC016D] 軍艦ゲーム

更差的阅读体验

---

停止学习没用的算法。去做点题。学习如何使用二分查找。

---

假设 \(a_u\) 表示进入点 \(u\) 造成的伤害，\(h\) 表示血量上限。

首先我们不难设计 dp：\(f_{u, i}\) 表示位于点 \(u\)，血量为 \(i\)，到达终点的最短期望时间。那么最后的答案就是 \(f_{u, i}\)。

位于点 \(u\) 血量为 \(i\) 时，我们可以耗费 \(1\) 的时间随机行走一步，也可以耗费 \(h-i\) 的时间回到起点。可以写出以下转移：

\[f_{u, i} \leftarrow \min \{h-i+f_{1, h}, \frac{1}{deg_u} \sum_{(u, v) \isin G}(f_{v, i-a_v} + 1) \} \]

容易发现第二部分的转移是萌萌的，因为图是 DAG，直接转移没有后效性。但是第一部分让转移出现了后效性。

我们这样做：我们给 \(f_{1, h}\) 直接钦定一个值 \(A\)，然后上面转移方程右边的 \(f_{1, h}\) 我们直接用 \(A\) 替换。如果最后算出的 \(f_{1, h} = A\) 就说明这个 \(A\) 是我们想要的答案。

然后我们发现 \(A - f_{1, h}\) 这个式子具有单调性。容易发现当 \(A\) 增加 \(\delta\) 的时候，\(h - i + A\) 会增加 \(\delta\)，而每个 \(f_{v, i-a_v} + 1\) 至多增加 \(\delta\)。因此 \(f_{1, h}\) 的增加量会 \(\le \delta\)。因此当 \(A\) 增大的时候，\(A - f_{1, h}\) 也会增大。

我们要求的就是 \(A - f_{1, h}\) 的一个零点。显然这个零点是唯一的，在单调函数上面二分即可。check 的时候直接 DAG 上 dp 就行。

那么这道题就做完了，复杂度 \(O(nh \log \frac{V}{\varepsilon})\)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 106
using namespace std;
int n,m,h,a[N],deg[N],t[N]; double f[N][N];
vector<int> rG[N];
int check(double mid)
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=h;j++)f[i][j]=0;
    for(int i=1;i<=n;i++)
        if(!(t[i]=deg[i])) {q.push(i); for(int j=1;j<=h;j++)f[i][j]=(i==n?0:h-j+mid);}
    while(q.size())
    {
        int u=q.front(); q.pop();
        if(u!=1)for(int i=1;i<=h;i++)
            f[u][i]=min(f[u][i],h-i+mid);
        for(int v:rG[u])
        {
            for(int i=1;i<=h;i++)
                f[v][i]=(i<=a[u]?(h-i+mid):(f[v][i]+(f[u][i-a[u]]+1)/deg[v]));
            t[v]--; if(!t[v])q.push(v);
        }
    }
    return f[1][h]<mid;
}
main()
{
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1,u,v;i<=m;i++)
        scanf("%d%d",&u,&v),rG[v].push_back(u),deg[u]++;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    check(5);
    double l=0,r=1e7;
    while(r-l>1e-8)
    {
        double mid=(l+r)/2;
        if(check(mid))r=mid; else l=mid;
    }
    if(l>1e6)printf("-1\n");
    else printf("%.8lf\n",l);
    return 0;
}