「算法相关」WQS 二分

发表于 更新于 分类于
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() 与二分函数进行简单的修改，从而达到所要的效果。

参考文章