Dyd's Blog

He who has a strong enough why can bear almost any how.

LOJ539 旅游路线

Posted on In
Symbols count in article: 2.8k Reading time ≈ 3 mins.

神仙 dp

旅游路线

思路

看到 $n \le 100$ 和 $q_i \le n^2$ 感觉就是 dp ，设 $d[i, j, k]$ 表示“从点 $i$ 走，有 $j$ 的油量，当前剩余钱数为 $k$ 的最远距离”，每次询问枚举 $k$ ，答案显然在 $d[i, 0, k]$ 上，然后就有一个 $O(mCq + Tq)$ 的做法

发现 $C \le 10^5$ ，存到状态里面没有前途，考虑每次直接从下一次买油的地方转移，设 $d[i, j]$ 表示“从点 $i$ 出发，有 $j$ 的钱，下一次买油就在点 $i$ 的最远距离”，那么有：
$$
d[i, j] = \max(d[k, j - p[i]] + dis(i, k, c[i]))
$$
其中 $dis(x, y, c)$ 表示“从 $x$ 走到 $y$ ，走过不超过 $c$ 条边的最大边权和”，然后发现瓶颈转移到求 $dis$ 上

首先又可以搞一个 dp 来求 dis ，即枚举下一条边，有：
$$
dis(i, j, k) = \max(dis(l, j, k - 1) + val(i, l))
$$
其中 $val(x, y)$ 是边 $x \to y$ 的边权

不难发现这样求 $dis$ 绝对爆炸，因为神奇的 $C \le 10^5$

然后这里就有一个神仙操作了：我们发现，其实我们关心的是 $dis(i, j, c[i])$ 的值，也就是不必每个 $dis(i, j, k)$ 都求，且每次 $k$ 只会减少 $1$ ，于是可以用倍增预处理，设 $f[i, j, k]$ 表示“从 $x$ 走到 $y$ ，走过不超过 $2^k$ 条边的最大边权和”，有：
$$
f[i, j, k] = \max(f[i, l, k - 1] + f[l, j, k - 1])
$$
在得到 $f$ 后，设 $dis[i, j, k]$ 表示”考虑 $c[i]$ 的最低 $k$ 位的 $dis(i, j)$ “即可求出 $dis$

然后再看，发现瓶颈在于最后每次询问求答案的时候那个 $Tq$ ，但显然 $d[x][i] > d[x][j] (i > j)$ ，可以把枚举换成二分

总时间 $O(n^2q + n^3 \log C + T \log q)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define eb emplace_back
const int N = 100 + 50, M = 1000 + 100, T = 1e5 + 100, inf = 0x3f3f3f3f, D = 18;
int n, m, mxc, que, mxq;
int p[N], c[N];
struct Q{ int s, q, d; } q[T];
struct Edge{ int ne, ver, w; } e[M];
int h[N], idx;
int d[N * N][N], dis[N][N][D], f[N][N][D];
void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }
int find(int s, int dd, int rr)
{
    int l = 0, r = rr, mid, res = -1;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (d[mid][s] >= dd) res = rr - mid, r = mid - 1;
        else l = mid + 1; 
    }
    return res;
}
int main()
{
    std::memset(h, -1, sizeof h), idx = 0;
    scanf("%d %d %d %d", &n, &m, &mxc, &que);
    for (int i = 1; i <= n; ++i) scanf("%d %d", p + i, c + i), c[i] = std::min(c[i], mxc);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 0; k < D; ++k) f[i][j][k] = dis[i][j][k] = -inf;
    for (int i = 1, a, b, l; i <= m; ++i)
    {
        scanf("%d %d %d", &a, &b, &l);
        add(a, b, l);
        f[a][b][0] = l;
        if (c[a] & 1) dis[a][b][0] = l;
    }
    for (int i = 1; i <= n; ++i) f[i][i][0] = dis[i][i][0] = 0;
    for (int k = 1; k < D; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
            {
                for (int l = 1; l <= n; ++l) f[i][j][k] = std::max(f[i][j][k], f[i][l][k - 1] + f[l][j][k - 1]);
                f[i][j][k] = std::min(f[i][j][k], inf);
            }
    for (int k = 1; k < D; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
            {
                if ((c[i] >> k) & 1)
                    for (int l = 1; l <= n; ++l) dis[i][j][k] = std::max(dis[i][j][k], dis[i][l][k - 1] + f[l][j][k]);
                else dis[i][j][k] = dis[i][j][k - 1];
                dis[i][j][k] = std::min(dis[i][j][k], inf);
            }
    mxq = 0;
    for (int i = 1; i <= que; ++i)
    {
        scanf("%d %d %d", &q[i].s, &q[i].q, &q[i].d);
        mxq = std::max(mxq, q[i].q);
    }
    for (int i = 0; i <= mxq; ++i)
        for (int j = 1; j <= n; ++j) if (i >= p[j])
        {
            for (int k = 1; k <= n; ++k) d[i][j] = std::max(d[i][j], d[i - p[j]][k] + dis[j][k][D - 1]);
            d[i][j] = std::min(d[i][j], inf);
        }
    for (int i = 1, ans; i <= que; ++i) printf("%d\n", find(q[i].s, q[i].d, q[i].q));
    return 0;
}