题解：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;
}