「算法相关」WQS 二分

简述

闲话

wqs 二分最初由王钦石在他的 2012 年国家集训队论文中提出,而从 IOI 2016 的 Aliens 题目开始,这种方法开始逐步在竞赛圈中有了一定的地位。在国内我们一般称为「wqs 二分」,而在国外一般称为「Alien Trick」。

常见适用范围

应用 wqs 二分的一种常见的问题形式为:给定一些带有价值的物品,价值可以为负,对于物品的选择具有一定限制,求选定物品总价值最大/最小值。

大致思想

屑在前面

为了方便下面的讲解,这里结合例题 Tree I 来进行讲解。

题目大意:有一张无向带权连通图,每条边要么是黑色要么是白色,现指定要找到一棵恰有 \(N\) 条白边的最小生成树,输出最小边权和。

首先,我们将这个题面与上面的适用范围进行对号入座,“带权边”是“有价值的物品”,“恰有 \(N\) 条白边”和“生成树”都是“限制”,“最小生成树”意味着求最小值。

设计函数

我们首先设计函数 \(f(x)\) 表示当恰选择 \(x\) 条白边时的最小生成树权值和,容易发现在一个定值 \(x=c\)\(f(x)\) 一定是单调递减的,因为此时存在一条白边的权值小于选定边集中的黑边最大边权,于是此时随着需要的白边的数量增长,一定可以用边权更小的白边换掉边权较大的黑边,使得总边权变小;达到 \(c\) 后,每次用白边替换黑边一定会使得总的边权和变大,于是之后函数应当是单调递增的,可以看出函数图像应当是一个下凸壳,于是函数图像应当大致如下:

而且显然有 \[ \forall x_1<x_2<x_3,\quad \dfrac{f(x_1)-f(x_2)}{x_1-x_2}<\dfrac{f(x_2)-f(x_3)}{x_2-x_3} \] 这一点考虑 \(f(x)\) 的定义并采用反证法证明不难。也就意味着图像雀雀食食是下凸壳。

利用图像

现在我们得到了一个下凸壳,那么我们该如何利用呢?我们知道,对于任意一个斜率,一定最多有一条为该斜率的直线与凸壳相切与某一点;而且可以发现,对于本题的凸壳,斜率越小,对应的切点的横坐标一定越小,因而我们可以尝试二分这个斜率,来尝试得到这个切点,假设我们能够求得对应的 \(x\)\(f(x)\),我们就可以确定下一步二分的斜率应该更大还是更小,并得到对应的最小值。

那么,我们就需要知道如何计算 \(x\)\(f(x)\)。首先,我们知道一个下凸壳的性质:对于同一斜率 \(k\) 的直线过凸壳上一点,过切点的直线的纵轴截距最小,如下图所示。

根据直线方程,不难得到该截距为 \[ g(x)=f(x)-k\cdot x, \] 意味着 \(g(x)\) 为选取 \(x\) 条白边时,每条白边价值减 \(k\) 后,此时能拿到的最优解。

这里给出一个性质:切点上的 \(g(x)\) 为每一条白边价值减去 \(k\) 后,没有额外限制(即不限制白边数量)选取得到的全局最优解。

这个结论看起来总觉得怪怪的,给人一种想推翻它的冲动,但是我们来看:对于任意一点 \((x,f(x))\),对应的是选取恰好 \(x\) 个白边时对应的最优解,加入我们将所有边的边权都减少 \(k\),显然任意两条边之间的相对大小关系是不变的,那么选择的边集并不会改变,于是这个最优解就变为了 \(f(x)-k\cdot x\),也就是 \(g(x)\),也就是直线的纵轴截距;而根据我们上面提到的下凸壳的性质,我们可以知道,过切点 \((a,f(a))\) 的直线的纵轴截距一定是所有截距中最小的,也就是所有 \(g(x)\) 中最小的,于是也就是不加限制选择白边的最优解,注意得到该最优解需要选出的白边数量一定是 \(a\),而加上 \(k\cdot a\) 得到的就是 \(f(a)\).

于是我们就可以在每一次二分斜率 \(k\) 后,直接求出当前每个白边边权减小 \(k\) 后任意选的最优解,同时记录最优解需要的白边数量 \(x\),再把价值加上 \(k\cdot x\) 就得到了所需的数据。

细节处理

事实上,真实的图像有可能是这样的:

注意到,图中的点 \(I\) 是无法被直线恰好切到的,因为它两边的直线的斜率相等,那么该如何处理?

我们可以使每次选取边时,对于权值相同的边,优先选白边,这样,我们得到的“切点”就是点 \(F\),在二分时我们保存的直线的斜率应当是满足需要的白边数大于等于 \(N\) 中的最小斜率,这样我们可以保证得到的斜率 \(k\) 正确,一定可以得到正确的纵轴截距,最后单独加上 \(k\cdot N\) 即可。

代码实现

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
const int N = 100010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}

struct Edge {int u, v, w, col;} e[N];
struct UnionSet {
int fa[N], siz[N], cnt;

inline UnionSet() {cnt = 0;}
inline void init(int x) {cnt = 0; while (cnt <= x) fa[cnt] = cnt, siz[cnt ++] = 1;}
int find(int x) {while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x;}
inline bool connected(int x, int y) {return find(x) == find(y);}
inline void unify(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (siz[x] > siz[y]) swap(x, y);
fa[x] = y, siz[y] += siz[x];
}
} us;

int n, m, ned, ans;

inline bool cmp(Edge x, Edge y) {return x.w == y.w ? x.col < y.col : x.w < y.w;}

inline int kruscal() {
int wcnt = 0; us.init(n); ans = 0;
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= m; ++ i) {
if (us.connected(e[i].u, e[i].v)) continue;
us.unify(e[i].u, e[i].v);
wcnt += !e[i].col, ans += e[i].w;
}
return wcnt;
}

inline int check(int x) {
for (int i = 1; i <= m; ++ i)
e[i].w -= e[i].col ? 0 : x;
int res = kruscal();
for (int i = 1; i <= m; ++ i)
e[i].w += e[i].col ? 0 : x;
return res;
}

int main() {
read(n), read(m), read(ned);
for (int i = 1; i <= m; ++ i)
read(e[i].u), read(e[i].v), read(e[i].w), read(e[i].col);
int l = -100, r = 100, res = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid) < ned) l = mid + 1;
else res = mid, r = mid - 1;
}
check(res); printf("%d", ans + res * ned); return 0;
}

简单总结

从上面的过程不难看出, wqs 二分适用于价值函数为上/下凸壳的情况,可以巧妙地将原本选择的部分限制去掉,从而优化算法。

同时如果遇到了图像上的一些特殊情况,可以对 check() 与二分函数进行简单的修改,从而达到所要的效果。

参考文章