题解 CF553E 【Kyoya and Train】
xht
2020-02-06 23:51:09
# 请到博客中查看
> [CF553E Kyoya and Train](https://codeforces.com/contest/553/problem/E)
## 题意
- 给定一张 $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}$ 即可。
## 代码
```cpp
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$