CF605E Intergalaxy Trips 题解

题意：

给定 \(n\) 个点的有向完全图。

\(i \to j\) 的边每天出现的概率均为 \(p_{i,j}\)，若 \(i = j\)，有 \(p_{i,j} = 1\)。

每天可以选择一条存在的出边走过去或停留在原地不动。

求最优策略下从 \(1\) 到 \(n\) 的期望天数，\(n \le 10^3\)。

完整题意：

最近，科学家们发现了虫洞 —— 宇宙中的一种物体，可以让你在星系和恒星系统之间旅行很长的距离。

科学家们知道有 \(n\) 个星系可以到达。你位于星系编号 \(1\)，你需要到达星系编号 \(n\)。从星系 \(i\) 到星系 \(j\)，你需要乘坐虫洞 \((i,j)\)，并在恰好一个星系日内，你将出现在星系 \(j\)。

不幸的是，所需的虫洞并不总是可用的。每个星系日它们会随机消失和出现。然而，虫洞的状态在一个星系日内不会改变。从星系 \(i\) 到星系 \(j\) 的虫洞每天分别存在的概率为 \(p_{ij}\)。你可以随时了解当前存在哪些虫洞。在每个时刻，你可以选择通过现有虫洞之一前往另一个星系，或者你可以等待一个星系日，看看哪些虫洞将在第二天将你带到下一个位置。

你的任务是找到从星系 \(1\) 到星系 \(n\) 旅行所需时间的期望值，如果你采取最佳方式行动。保证该期望值存在。

输入格式：

输入的第一行包含一个整数 \(n\)（\(1 \leq n \leq 1000\)）—— 可以到达的星系数量。

然后是一个 \(n\) 行 \(n\) 列的矩阵。每个元素 \(p_{ij}\) 代表从星系 \(i\) 到星系 \(j\) 存在虫洞的概率。所有概率以百分比表示，为整数。保证主对角线上的所有元素均为 \(100\)。

输出格式：

输出一个实数值 —— 如果采取最佳方式行动，从星系 \(1\) 到星系 \(n\) 旅行所需时间的期望值。你的答案将被视为正确，如果其绝对或相对误差不超过 \(10^{-6}\)。

具体来说：假设你的答案是 \(a\)，而评审的答案是 \(b\)。检查程序将认为你的答案是正确的，如果 \(\frac{|a-b|}{\max(1, b)} \leq 10^{-6}\)。

考虑设 \(f_i\) 为 \(i \to n\) 的期望耗时，那么显然我们不会跑到一个 \(f_j > f_i\) 的地方碰运气。

因此我们只需要考虑比它更优的点。那么什么是更优的点呢？就是所有冒出来的边 \((i,j)\) 中 \(f_j\) 最小的那个 \(j\)

考虑用转移方程的形式描述这个过程： \[ f_i=\sum_j^{f_j<f_i} p_{i, j} f_j \prod_k^{f_k<f_j}\left(1-p_{i, k}\right)+f_i \prod_j^{f_j<f_i}\left(1-p_{i, j}\right)+1 \] 第一部分枚举 \(j\) ， \(j\) 的限制就是没有 \(k(k\ne j)\) 满足 \(f_k < i\) 且 \((i,k)\) 存在。

第二部分就是实在找不出这么个 \(j\) 能走了，那就在原地绕一圈。第三部分的 \(1\) 很好理解吧。

则移项可得 \[ f_i=\frac{\sum_j^{f_j<f_i} p_{i, j} f_j \prod_k^{f_k<f_j}\left(1-p_{i, k}\right)+1}{1-\prod_j^{f_j<f_i}\left(1-p_{i, j}\right)} \] 这个方程直接枚举看上去没法优化，因此我们不妨观察一下有什么特殊性质。

首先容易发现每次更新 \(i\) 的 \(j\) ，显然在每次更新后是单调不增的，并且 \(f_i\) 一定大于 \(f_j\) 。

那么如果我们找到一个最小的 \(f_x\) 作为 \(f_j\) ，然后去更新其他的 \(f_i\) ，是不是就可以了呢？

这个过程有点像 Dijkstra ，每次找出最小的 \(u\) ，去尝试更新所有相邻的 \(v\) 。

不妨记 \(g_i\) 为分数线上面一坨， \(h_i = \prod_j^{f_j<f_i}\left(1-p_{i, j}\right)\) ，即 \(f_i = \dfrac{g_i}{1 - h_i}\) 。

具体地，我们将 \(f_i,g_i,h_i(i<n)\) 初始都设为 \(1\) ，并把 \(n\) 作为初始的 \(j\) ，

然后每轮都枚举未被作为 \(j\) 过的 \(i\) ，通过新考虑 \((i,j)\) 的贡献（注意是有向完全图，所以不是 \((j,i)\) ）

如果按 \(g_i,h_i,f_i\) 依次更新的话，那么在 \(h_i\) 被 \(j\) 更新之前，可以通过 \(g_i\gets g_i + p_{i,j}f_jh_i\) 以达到目的。

因为这时的 \(h_i\) 就等于 \(\prod_k^{f_k<f_j}\left(1-p_{i, k}\right)\) ，换句话说，截止到 \(j\) ，其他所有已经考虑过的点 \(k\) 都有 \(f_k < f_j\)

时间复杂度 \(\mathcal{O}(n^2)\) ，注意不要用 cin 读 double 型数据，否则会 TLE

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

int n,cnt,q[N]; char vis[N];
double p[N][N],f[N],g[N],h[N];
void upd()
{
    int j = q[cnt];
    for(int i = 1; i <= n; i++)
    {
        if(vis[i]) continue;
        g[i] += f[j] * p[i][j] * h[i];
        h[i] *= 1 - p[i][j]; f[i] = g[i] / (1 - h[i]);
    }
}
void solve()
{
    for(int i = 1; i < n; i++) f[i] = g[i] = h[i] = 1;
    f[n] = 0; h[n] = 1; vis[n] = true; q[++cnt] = n; upd();
    for(; cnt < n; ) {
        int id; double v = INF;
        for(int i = 1; i <= n; i++)
            if(!vis[i] && f[i] < v) v = f[i], id = i;
        vis[id] = true; q[++cnt] = id; upd();
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; if(n == 1) return cout << "0\n", 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1, x; j <= n; j++) cin >> x, p[i][j] = x / 100.0;
    solve(); cout << fixed << setprecision(8) << f[1] << '\n';
    return 0;
}