CF553E Kyoya and Train 题解

作者: xht37 分类: 题解 发布时间: 2020-02-06 14:44

Visits: 224

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$

发表评论

电子邮件地址不会被公开。 必填项已用*标注