题解 CF605E 【Intergalaxy Trips】

· · 题解

\mathrm{Problem}

\mathrm{Solution}

搞了一天的期望神题

我们设 E_x 表示节点 x 接下来要到节点 n 的期望天数。

有一些显然但很重要的结论，就是：

对于结论2：当 x 已经被若干点更新过了，此时枚举到 y 了，如果你计算了 y 的贡献那么一定会使当前节点 x 的期望值增加，因此 x 一定不会被 y 更新到。

因此我们便有了算法的大致思路：每一次都寻找一个期望值最小的点，并固定这个点的期望值；同时也用这个点的期望值去更新未被更新的期望值。

该算法的思路与Dijkstra算法类似。

考虑如何转移：我们发现若我们要转移节点 i，需要保证 \forall j 在E_j<E_i的情况下通道是关闭的，因为上面提到贪心的原则是选取期望值最小的节点，且 i 的通道是开的。因此假设已经完成转移的点为a_1,a_2,...,a_m且满足E_1<E_2<...<E_m。

E_i=\sum_{j=1}^{m} E_{a_j}\times p_{i,a_j} \prod_{k=1}^{j-1} (1-p_{i,a_k})

观察到我们此时计算的 E_i 仅仅是与 i 相连的通道中至少一条开启时的贡献，可能存在通道一条都不开启的情况。我们发现，通道每条都不开启的概率为\sum p_{i,j},则通道至少开启的概率为1-\sum p_{i,j}，则至少一条开启的天数是：\frac{1}{1-\sum p_{i,j}}。

因此我们的期望天数就变成了E_x/(1-\prod_{y}^{E_y<E_x}p_{x,y})。

则上述转移方程就变成了：

E_i=\sum_{j=1}^{m}[E_{a_j}/(1-\prod_{k}^{E_{a_k}<E_{a_j}}p_{a_j,a_k})]\times p_{i,a_j} \prod_{k=1}^{j-1} (1-p_{i,a_k})

然后就可以愉快的转移辣

\mathrm{Code}

#include <bits/stdc++.h>

using namespace std;
const int N = 2000;

int n;
int vis[N];
double s[N], P[N][N], E[N];

int read(void)
{
    int s = 0, w = 0; char c = getchar();
    while (!isdigit(c)) w |= c == '-', c = getchar();
    while (isdigit(c)) s = s*10+c-48, c = getchar();
    return w ? -s : s;
}

int main(void)
{
    n = read();
    for(int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            P[i][j] = 1.0 * read() / 100.0;
    if (n == 1) return puts("0"), 0;
    vis[n] = 1, E[n] = 0;
    for (int i=1;i<=n;++i) {
        E[i] = 1;
        s[i] = 1 - P[i][n];
    }
    for (int i=1;i<=n;++i)
    {
        int p = 0;
        double Min = 1e18;
        for (int j=1;j<=n;++j) 
            if (vis[j] == 0 && 1.0 * E[j] / (1 - s[j]) < Min) 
                Min = 1.0 * E[j] / (1 - s[j]), p = j;
        vis[p] = 1;
        if (p == 1) return printf("%.15lf\n", Min) * 0;
        for (int j=1;j<=n;++j)
            E[j] += 1.0 * E[p] / (1 - s[p]) * P[j][p] * s[j], s[j] *= 1.0 - P[j][p];
    }
    return 0;
}