题解 CF605E 【Intergalaxy Trips】

## $\mathrm{Problem}$ - $n$ 个点的有向完全图。 - $i \to j$ 的边每天出现的概率均为 $p_{i,j}$，若 $i = j$，有 $p_{i,j} = 1$。 - 每天选择一条存在的出边走过去。 - 求最优策略下从 $1$ 到 $n$ 的期望天数。 - $n \le 10^3$。 --- ## $\mathrm{Solution}$ ~~搞了一天的期望神题~~ 我们设 $E_x$ 表示节点 $x$ 接下来要到节点 $n$ 的期望天数。 有一些显然但很重要的结论，就是： - 节点 $x$ 接下来转移的点一定是当前开放的出边中 $E$ 值最小的一个点。 - 对于若存在 $x,y$ 满足 $E_x<E_y$，则 $x$ 的期望决策点一定不包含$y$。 对于结论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}$ ```cpp #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; } ```