CF553E Kyoya and Train 题解

CF553E Kyoya and Train

题意

给定一张 $n$ 个点 $m$ 条边的无重边无自环的有向图，你要从 $1$ 号点到 $n$ 号点去。
如果你在 $t$ 时刻之后到达 $n$ 号点，你要交 $x$ 元的罚款。
每条边从 $a_i$ 到 $b_i$ ，走过它需要花费 $c_i$ 元，多次走过同一条边需要多次花费。
走过每条边所需的时间是随机的，对于 $k \in [1,t]$ ， $\frac{p_{i,k}}{10^5}$ 表示走过第 $i$ 条边需要时间 $k$ 的概率。因此如果多次走过同一条边，所需的时间也可能不同。
你希望花费尽可能少的钱（花费与罚款之和）到达 $n$ 号点，因此每到达一个点，你可能会更改原有的计划。
求在最优决策下，你期望花费的钱数。
$n \le 50$ ， $m \le 100$ ， $t \le 2 \times 10^4$ ， $x,c_i \le 10^6$ ， $\sum_{k=1}^t p_{i,k} = 10^5$ ，答案精度误差 $\le 10^{-6}$ 。

题解

首先给出暴力 dp 的形式：

设 $f_{i,j}$ 表示到点 $i$ 且已经过去 $j$ 时间后，在最优决策下的最小花费，则我们的目标即为 $f_{1,0}$ 。

转移如下： $f_{i,j} = \begin{cases}0 & i = n, j \le t \\\\ x & i = n, j > t \\\\ \operatorname{dist}(i, n) + x & i \ne n, j \ge t \\\\ \min_{a_k = i} \left(\sum_{l=1}^t p_{k,l}f_{b_k,j+l} + c_k\right) & i \ne n, j < t \\\\ \end{cases}$

其中 $\operatorname{dist}(x,y)$ 表示 $x \to y$ 的最小花费。

考虑这个 dp 的正确性，由于转移时 $j$ 严格变小，因此这个 dp 实际上是个 DAG。

直接做的话，总转移数是 $\mathcal O(mt)$ 的，每次转移需要 $\mathcal O(t)$ ，总时间复杂度 $\mathcal O(mt^2)$ ，显然不够优秀。

注意到 $\sum_{l=1}^t p_{k,l}f_{b_k,j+l}$ 是一个卷积，考虑分治 FFT 优化，时间复杂度降为 $\mathcal O(mt\log^2 t)$ 。

另外，在算 $\operatorname{dist}(x,y)$ 的时候可以 Floyd，时间复杂度 $\mathcal O(n^3)$ 。

接下来我们具体来实现一下分治 FFT，首先处理出 $f_{*,t\dots 2t-1}$ 和 $f_{n,*}$ ，为了方便，可以先去掉 $n$ 的所有出边。

再设 $g_{i,j}$ 表示在时刻 $j$ 选择走第 $i$ 条边以及之后的最小花费，则有 $f_{a_i,j} \leftarrow g_{i,j}$ 。

对于 $g_{*,l\dots r}$ ，我们先计算 $g_{*,mid+1\dots r}$ 并求出 $f_{*,mid+1\dots r}$ ，再考虑 $f_{*,mid+1\dots r}$ 对 $g_{*,l\dots mid}$ 的贡献，最后计算 $g_{*,l\dots mid}$ 。

考虑对于 $x \in [l,mid],i \in [1,m]$ ，设 $y = b_i$ ， $f_{y,mid+1\dots r}$ 对 $g_{i,x}$ 的贡献为： $\sum_{j=mid+1}^{r} p_{i,j-x}f_{y,j}$ 设 $a_j = p_{i,j+1},b_j=f_{y,r-j}$ ，则转化为： $\sum_{j=0}^{r-mid-1} a_{j+mid-x}b_{r-mid-1-j}$ FFT 即可。

需要注意的是，由于我们 CDQ 分治的时候只分治 $0\sim t - 1$ ，因此 $t \sim 2t-1$ 的贡献需要先额外计算，这部分并不会影响时间复杂度。

当然，还可以分治 $0\sim 2t-1$ ，但是在第一层分治时跳过计算 $f_{mid+1 \dots r}$ 即可。

代码

namespace FFT {
	const int N = 1 << 21 | 1;
	const double PI = acos(-1);
	struct I {
		double x, y;
		inline I() {}
		inline I(double x, double y) : x(x), y(y) {}
		inline I &operator = (int o) { return x = o, y = 0, *this; }
		inline I &operator = (double o) { return x = o, y = 0, *this; }
		inline I operator + (const I o) const { return I(x + o.x, y + o.y); }
		inline I operator - (const I o) const { return I(x - o.x, y - o.y); }
		inline I operator * (const I o) const {
			return I(x * o.x - y * o.y, x * o.y + y * o.x);
		}
	} a[N], b[N];
	inline void rd(I &x) { int o; ::rd(o), x = o; }
	inline void print(I x, char k = '\n') { ::print((int)(x.x + 0.5), k); }
	int n, m, k, l, r[N];
	inline void fft(I *a, int n, int x) {
		for (int i = 0; i < n; i++) if (i < r[i]) swap(a[i], a[r[i]]);
		for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) {
			I W = I(cos(PI / k), x * sin(PI / k));
			for (int i = 0; i < n; i += o) {
				I w = I(1, 0);
				for (int j = 0; j < k; j++, w = w * W) {
					I x = a[i+j], y = w * a[i+j+k];
					a[i+j] = x + y, a[i+j+k] = x - y;
				}
			}
		}
	}
	inline void solve() {
		k = 1, l = 0;
		while (k <= n + m) k <<= 1, ++l;
		for (int i = 0; i < k; i++)
			r[i] = (r[i>>1] >> 1) | ((i & 1) << (l - 1));
		for (int i = n + 1; i < k; i++) a[i] = 0;
		for (int i = m + 1; i < k; i++) b[i] = 0;
		fft(a, k, 1), fft(b, k, 1);
		for (int i = 0; i < k; i++) a[i] = a[i] * b[i];
		fft(a, k, -1);
		for (int i = 0; i <= n + m; i++) a[i].x /= k;
	}
}

const int N = 53, M = 107, T = 2e4 + 7;
const double inf = 1e18;
int n, m, t, x, a[M], b[M];
double d[N][N], c[M], p[M][T*2], f[N][T*2], g[M][T];

void cdq(int l, int r) {
	if (l == t) return;
	if (l == r) {
		for (int i = 1; i < n; i++) f[i][l] = inf;
		for (int i = 1; i <= m; i++)
			if (a[i] != n) f[a[i]][l] = min(f[a[i]][l], g[i][l] + c[i]);
		return;
	}
	int mid = (l + r) >> 1;
	cdq(mid + 1, r);
	FFT::n = r - l - 1, FFT::m = r - mid - 1;
	for (int i = 1; i <= m; i++)
		if (a[i] != n) {
			for (int j = 0; j <= FFT::n; j++) FFT::a[j] = p[i][j+1];
			for (int j = 0; j <= FFT::m; j++) FFT::b[j] = f[b[i]][r-j];
			FFT::solve();
			for (int j = l; j <= mid; j++) g[i][j] += FFT::a[r-j-1].x;
		}
	cdq(l, mid);
}

int main() {
	rd(n), rd(m), rd(t), rd(x);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j) d[i][j] = inf;
	for (int i = 1, x; i <= m; i++) {
		rd(a[i]), rd(b[i]), rd(x), c[i] = d[a[i]][b[i]] = x;
		for (int j = 1; j <= t; j++) rd(x), p[i][j] = x / 1e5;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	for (int i = 0; i < 2 * t; i++) f[n][i] = i <= t ? 0 : x;
	for (int i = 1; i < n; i++)
		for (int j = t; j < 2 * t; j++)
			f[i][j] = d[i][n] + x;
	cdq(0, 2 * t - 1);
	printf("%.10f\n", f[1][0]);
	return 0;
}

$\textstyle$

题意

题解

代码

评论