Visits: 441

CF605E Intergalaxy Trips

题意

• $n$ 个点的有向完全图。
• $i \to j$ 的边每天出现的概率均为 $p_{i,j}$，若 $i = j$，有 $p_{i,j} = 1$。
• 每天选择一条存在的出边走过去。
• 求最优策略下从 $1$ 到 $n$ 的期望天数。
• $n \le 10^3$。

题解

最优策略显然应该是贪心的找出边中期望天数尽量小的走过去，那么反向推一次，每次找当前期望天数最小的点，然后动态维护期望天数和剩余概率即可，时间复杂度 $\mathcal O(n^2)$。

代码

const int N = 1e3 + 7;
int n, v[N];
ld p[N][N], a[N], d[N];

inline bool work() {
    int o;
    ld x = 1e100L;
    for (int i = 1; i <= n; i++)
        if (!v[i] && (d[i] + a[i]) / (1 - a[i]) <= x) x = (d[i] + a[i]) / (1 - a[i]), o = i;
    v[o] = 1, d[o] = (d[o] + a[o]) / (1 - a[o]);
    if (o == 1) return 1;
    for (int i = 1; i <= n; i++)
        if (!v[i]) d[i] += a[i] * p[i][o] * (d[o] + 1), a[i] *= 1 - p[i][o];
    return 0;
}

int main() {
    rd(n);
    for (int i = 1, x; i <= n; i++) {
        for (int j = 1; j <= n; j++) rd(x), p[i][j] = 0.01L * x;
        a[i] = 1;
    }
    a[n] = 0;
    for (int i = 1; i <= n; i++)
        if (work()) return cout << fixed << setprecision(15) << d[1] << endl, 0;
    return 0;
}