CF605E Intergalaxy Trips 题解

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;
}