Zth's Blog

记录学习路上的点滴

0%

Convex Hull Trick cf816e

发表于 分类于

cf816e， Convex Hull Trick算法学习笔记

Convex Hull Trick

以最小值为例， 最大值同理

作用

给出$n$个形如$y = k_i x + b_i$的一次函数和$q$个$x$询问每个$x_i$在这$n$个一次函数中能取到的最小\大值， 询问必须离线

原理及实现

原理

对于给出的这$n$个函数中的每一个， 我们只保留它当作最小值的那一段， 如图(来自PEGWiki)所示， 共有四个函数， 绿色的部分是我们保留的

这样做完之后我们记录了保留的这些函数本身和它们的交点， 询问$x$时只需要二分找到$x$在哪一段里就可以了

实现

下面讲讲怎么找出这些有用的最小值段

不难看出这些线段一定是组成一个凸包， 因为从左到右这些线段的斜率一定是不断减小的， 那我们就首先把这$n$个函数按照斜率从小到大排好序， 然后尝试挨个添加到存好的段里

假设按斜率从小到大有$l_1, l_2, l_3$三个函数， $Insect(l_i, l_j)$是两条函数的交点， 那么如果$Insect(l_3, l_1) > Insect(l_2, l_1)$， 那么$l_2$的那一段应该被保留， 我们求出$Insect(l_3, l_2)$之后添加这个交点和$l_3$就可以了； 反之如果有$Insect(l_3, l_1) < Insect(l_2, l_1)$，那么$l_2$与$l_1$的那一段就没有意义了， 我们删除$l_2$和$Insect(l_2, l_1)$， 添加$l_3$和$Insect(l_3, l_1)$

上述操作在类似单调栈的过程中进行， 当栈内元素数量$\geq 2$时， 先不断尝试用要添加的函数去删除栈顶的函数和其对应的交点然后再添加这个函数和对应的交点

这样做完后的交点一定是从小到大排好序的， 询问时二分找到交点在那个段里就好了

代码

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
struct Line
{
    long long k, b;
};

// 要保证添加的函数是按斜率从小到大排好的
struct Cht
{
    int ls; // 栈内的函数(有用段)数量
    double isct[112345]; // 交点
    Line line[112345]; // 栈内函数的表达式

    void Init() // 初始化
    {
        ls = 0;
        line[0] = (Line){0, 0}; // 这个有没有都行
    }

    double Insect(Line a, Line b) // 求交点
    {
        double k1 = 1.0 * a.k, b1 = 1.0 * a.b, k2 = 1.0 * b.k, b2 = 1.0 * b.b;

        return (b2 - b1) / (k1 - k2);
    }

    void Insert(Line x) // 尝试添加一个新的函数
    {
        while(ls >= 2 && Insect(line[ls - 1], x) <= Insect(line[ls - 1], line[ls])) ls --; // 不断删除没有用的栈顶函数

        isct[ls] = Insect(line[ls], x); // 记录交点
        line[++ ls] = x; // 记录函数
      	// 这样写的话二分查找到的交点编号和函数编号是一致的
    }

    long long Query(int qx) // 询问qx的最小值
    {
        int p = std:: lower_bound(isct + 1, isct + ls, qx) - isct;

        return 1LL * line[p].k * qx + line[p].b;
    }
} cht;

E. Long Way Home

题目描述

给定一个$n$个点， $m$条边的无向带权图， 另外每两个点之间有一种带权通道， 点$u$到点$v$之间的通道权值为$(u - v)^2$， 另外给出一个$k$， 代表你最多可以走$k$条通道， 问你从$1$号点到每个点的距离最小值是多少

数据范围

$2 \leq n \leq 10^5, 1 \leq m \leq 10^5, 1 \leq k \leq 20$

题解

Hint1

对于每个点， 怎么求出以一条通道结尾的距离最小值？

这个简单， 只要先跑完一遍Dijkstra()然后用每个点的$d[]$加上一条通道去更新别的点的距离就好了

Hint2

如果$k = 1$， 该怎么做？

如果$1$到点$i$的路径上我们走了一条$u$到$v$的通道， 那么这条路径可以分为三部分：

  1. $1$到$u$的路径， 全是图上的边
  2. $u$到$v$的通道
  3. $v$到$i$的路径， 全是图上的边

先用Hint1的的方法， 再把更新后的每个点加入队列再跑一遍Dijkstra()就可以了， 可是这样会不会出现一条路径上用了多个通道呢？ 答案是不会， 因为跑Dijkstra()的过程中用的全是图上的边

Hint3

假设已经知道了$k = i$的结果， 怎么求出$k = i + 1$的？

在Hint2的基础上， 使用$d_{old}[]$（这就是$k = i$时的答案）加上一条通道去更新别的点的距离， 再把更新的点加入队列跑一遍Dijkstra()就可以了

Solution

以上Hint已经可以导出正解了

但是显然Hint1中的操作是要$O(n^2)$的， $10^5$的数据肯定是过不了， 要考虑优化

我们设$d_{old}[]$表示的是在$k = i$时的答案， $d_{new}[]$是在$k = i$的答案的基础上最后加一条通道(也可以不加)更新出的距离

那么对于每个$v$有

固定$v$， 设$tmp = d_{old}[u] + (u - v)^2$， 改写一下

所以

因为$v$固定， 所以可以把$v^2$单独拿出来， 设$y = -2uv + d_{old}[u] + u^2$， 则对于每个$u$都是一个以$v$为变量的函数

问题等价于对这$n$个函数求$v = 1, 2, \cdots, n$时的最小值， 这个时候就可以用上面讲的Convex Hull Trick了

代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

int n, m, ks;
struct Edge
{
    int from, to, next, cost;
} edge[212345];
int head[112345], tot;
long long d[112345];

struct Line
{
    long long k, b;
};

struct Node
{
    int pos;
    long long dist;

    bool operator < (Node tmp) const
    {
        return dist > tmp.dist;
    }
};
std:: priority_queue<Node> pq;

void Addedge(int u, int v, int e)
{
    edge[++ tot] = (Edge){u, v, head[u], e};

    head[u] = tot;
}

struct Cht
{
    int ls;
    double isct[112345];
    Line line[112345];

    void Init()
    {
        ls = 0;
        line[0] = (Line){0, 0};
    }

    double Insect(Line a, Line b)
    {
        double k1 = 1.0 * a.k, b1 = 1.0 * a.b, k2 = 1.0 * b.k, b2 = 1.0 * b.b;

        return (b2 - b1) / (k1 - k2);
    }

    void Insert(Line x)
    {
        while(ls >= 2 && Insect(line[ls - 1], x) <= Insect(line[ls - 1], line[ls])) ls --;

        isct[ls] = Insect(line[ls], x);
        line[++ ls] = x;
    }

    long long Query(int qx)
    {
        int p = std:: lower_bound(isct + 1, isct + ls, qx) - isct;

        return 1LL * line[p].k * qx + line[p].b;
    }
} cht;

void Dijkstra()
{
    while(! pq.empty())
    {
        int u = pq.top().pos;
        long long dis = pq.top().dist;
        pq.pop();

        if(d[u] != dis) continue;

        for(int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            long long e = edge[i].cost;

            if(d[u] + e < d[v])
                d[v] = d[u] + e, pq.push((Node){v, d[v]});
        }
    }
}

void Solve()
{
    d[1] = 0;
    for(int i = 2; i <= n; i ++) d[i] = 1e18;

    pq.push((Node){1, 0});
    Dijkstra();

    for(int i = 1; i <= ks; i ++)
    {
        cht.Init();
        for(int j = 1; j <= n; j ++) cht.Insert((Line){-2LL * j, d[j] + 1LL * j * j});
        for(int j = 1; j <= n; j ++) d[j] = std:: min(d[j], cht.Query(j) + 1LL * j * j);

        for(int j = 1; j <= n; j ++) pq.push((Node){j, d[j]});
        Dijkstra();
    }

}

int main()
{
    scanf("%d%d%d", &n, &m, &ks);
    for(int i = 1; i <= m; i ++)
    {
        int u, v, e;
        scanf("%d%d%d", &u, &v, &e);

        Addedge(u, v, e);
        Addedge(v, u, e);
    }

    Solve();

    for(int i = 1; i <= n; i ++) printf("%lld%c", d[i], " \n"[i == n]);

    return 0;
}