Description

题目链接

Solution

首先用 Floyd 处理两点间最短路。

在这里有两个小坑点,下文会提到。

设 $f(i, j, 0/1)$ 表示前 $i$ 节课,换了 $j$ 个教室,当前课程换 / 不换教室的期望。设 $w(i, j)$ 为两点间最短路的距离,那么有:

$$ f(i, j, 0) = \min \{f(i - 1, j, 0) + w(c_{i - 1}, c_i), f(i - 1, j, 1) + w(d_{i - 1}, c_i) \cdot k_{i - 1} + w(c_{i - 1}, c_i) \cdot (1 - k_{i - 1})\} $$

$$ f(i, j, 1) = \min \{f(i - 1, j - 1, 0) + w(c_{i - 1}, d_i) \cdot k_i + w(c_{i - 1}, c_i) \cdot (1 - k_i), f(i - 1, j - 1, 1) + w(c_{i - 1}, c_i) \cdot (1 - k_{i - 1}) \cdot (1 - k_i) + w(c_{i - 1}, d_i) \cdot (1 - k_{i - 1}) \cdot k_i + w(d_{i - 1}, c_i) \cdot k_{i - 1} \cdot (1 - k_i) + w(d_{i - 1}, d_i) \cdot k_{i - 1} \cdot k_i \} $$

我知道没人会看完上面这个式子的。

其实就是把期望的公式往里一套。

答案为 $\min \limits_{i = 0}^m \{f(n, i, 1/0)\}$。

运行!结果怎么是负数?

第一个坑点:邻接矩阵初始值不能太大,不然会相加爆 long long

改完了,运行!结果怎么比答案大?

如果上一次的教室在 $1$ 号点,这一次仍然在 $1$ 号点,那么其实是不需要移动的。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

LL g[310][310];
double f[2010][2010][2];
double k[2010];
double ans = 1e18;
int c[2010], d[2010];
int n, m, v, e;

int main() {
    read(n), read(m), read(v), read(e);
    for (int i = 1; i <= v; ++i) {
        for (int j = 1; j <= v; ++j) {
            g[i][j] = 1e9;
        }
    }
    for (int i = 1; i <= n; ++i)    read(c[i]);
    for (int i = 1; i <= n; ++i)    read(d[i]);
    for (int i = 1; i <= n; ++i)    scanf("%lf", &k[i]);
    for (int i = 1, a, b, w; i <= e; ++i) {
        read(a), read(b), read(w);
        g[a][b] = std::min(g[a][b], 1LL * w);
        g[b][a] = std::min(g[b][a], 1LL * w);
    }
    for (int p = 1; p <= v; ++p) {
        for (int i = 1; i <= v; ++i) {
            for (int j = 1; j <= v; ++j) {
                g[i][j] = std::min(g[i][j], g[i][p] + g[p][j]);
            }
        }
    }
    for (int i = 1; i <= v; ++i)    g[i][i] = 0;
    memset(f, 0x7f7f7f7f, sizeof(f));
    f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j <= std::min(i, m); ++j) {
            f[i][j][0] = std::min(f[i - 1][j][0] + g[c[i - 1]][c[i]], f[i - 1][j][1] + g[d[i - 1]][c[i]] * k[i - 1] + g[c[i - 1]][c[i]] * (1 - k[i - 1]));
            if (j)    f[i][j][1] = std::min(f[i - 1][j - 1][0] + g[c[i - 1]][d[i]] * k[i] + g[c[i - 1]][c[i]] * (1 - k[i]), f[i - 1][j - 1][1] + g[c[i - 1]][c[i]] * (1 - k[i - 1]) * (1 - k[i]) + g[c[i - 1]][d[i]] * (1 - k[i - 1]) * k[i] + g[d[i - 1]][c[i]] * (1 - k[i]) * k[i - 1] + g[d[i - 1]][d[i]] * k[i - 1] * k[i]);
        }
    }
    for (int i = 0; i <= m; ++i)    ans = std::min({ans, f[n][i][0], f[n][i][1]});
    printf("%.2lf\n", ans);
    return 0;
}
Last modification:September 3rd, 2021 at 03:15 am