【学习笔记】wqs 二分

· · 算法·理论

感觉是一个很神秘的东西。

例题

P2619 [国家集训队] Tree I

这题不算是 dp，但还是记 f_i 为恰好选 i 条白边的最小代价。而 wqs 二分的要求是函数要具有凸性。简单版本就是选东西，不断加入当前价值最大的边，简单分析一下即可。

我是这么理解的：设原图最小生成树白边数量为 x，按增加代价从小到大换边，当前肯定选代价最小的一种换边方式（不用管是几条），那么就满足凸性。

将 (i,f_i) 加入图中，则形成一个凸包（这里是下凸壳）。我们要求的就是第 k 个点的纵坐标 f_k。

对于下凸壳的题，不难想到用直线去扫。wqs 二分就是枚举直线的斜率 k，那么要求的是 k 对应的 x，然后根据 x 与 k 的关系缩小边界进行二分。

先给结论：对应的 x 是将所有白边权值减去 k 后最小生成树中白边的数量。

其实证明比较简单：设这条直线切凸壳与点 x，则其截距为 g_x=f_x-k\times x，如下图，相切就代表截距也就是 g_k 最小，也相当于相当于求一个 x 选 x 条白边时最小。(注：对于以下的所有图，请自行将横坐标间距认为成 1）

和之前不一样的是，这次多了一个 kx，但是可以提前把白边边权扣掉 k 时，选多少个，就多扣多少个 k，所以可以直接跑 kruskal。

tips：这里不要像我一样搞错逻辑，是 k 推出 x 和 g_x，而不是用已知 x 求 g_x！

求出 x 后，将 x 与 need 相比较，结合上面的过程可知：若 x>need，则说明扣太多，白色选太多了，要向下二分 k，否则向上二分。

对于二分的上下界，这里的 k 控制的是白色边的数量，当其大于值域后，白色能选的都选了，所以上界是 W，同理，下界是 -W。

但接下来才是 wqs 二分的精髓！

Q：首先，万一遇到下面这种情况，相邻直线斜率相同，切不到某一个点怎么办（又或者同时切到线段两端的点）？ A：这涉及到一个很重要的细节：对于权值相同的边，优先选白边。由于一定有解，取不到的点是因为 g_x 相同，其实也就是因为有白边减去 k 后和黑边权值相同，换不影响 g_x。

于是做出如上规定，尽量选白边，但相应地，同时也是 wqs 必须处理的一步：求出来的 x，\ge need 就要把 k 记录到 ans 中。

其实还有一种限制：尽量选黑边，在 x\le need 时记录答案，道理也是一样的。写法因人而异吧。

注意这是保证有解的情况，无解的情况后面有，处理一样，但判断会比较复杂。

Q：那最后减去的是 ans\times need 还是 ans\times 实际求出来的x？

A：无论 x 是否等于 need，f 都只减去 ans\times need。需要理解的是， k 二分的是 x 点可以被切到的斜率，而 g_x 是最优方案对应的截距。假如被切的点在同一条只直线上，那么这一串点 g_x 都是相等的，但减去的 x\times k 是不相等的，ans\times need 其实对应的是 x=need,k=ans。

Q：斜率 k 是否要用小数二分？\ A：不需要。由上一个问题对切相邻处理引出更广泛的问题：假设斜率 k 切到 <m，k+1 切到 >m 该怎么处理？其实对于相同权值之间的排序以及二分的处理，就已经解决了。

由于横纵坐标及斜率都是整数，根据上面，如果切不到，也一定能找到其和相邻节点的斜率，也可以找到答案。

其实程序中还有个小优化：可以把白边黑边存起来分别排序，由于白边减去 k 后相对大小不变，所以可以类似归并排序一样选边，就可以快速排序的 \log 去掉，但不写也没多大问题。我懒地写了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
const int M = 105;
struct node { int u, v, w, co; } e[N];
bool cmp(node x, node y) {//权值相同优先选白边 
    if (x.w != y.w) return x.w < y.w;
    else return x.co < y.co;
}
int n, m, k, sum, fa[N];
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
bool chk(int x) { // kruskal 最小生成树 
    for (int i = 1; i <= m; i++) 
        if (!e[i].co) e[i].w -= x;
    sort(e + 1, e + 1 + m, cmp);
    for (int i = 1; i <= n; i++) fa[i] = i;
    int s = 0, cnt = 0; sum = 0;
    for (int i = 1; i <= m; i++) {
        int tx = find(e[i].u), ty = find(e[i].v);
        if (tx == ty) continue; fa[tx] = ty;
        s += !e[i].co, cnt++, sum += e[i].w;
        if (cnt == n - 1) break;
    } for (int i = 1; i <= m; i++) 
        if (!e[i].co) e[i].w += x;
    return s >= k;
}
signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; e[i].u++, e[i].v++, i++)//注意题目中节点从 0 开始 
        cin >> e[i].u >> e[i].v >> e[i].w >> e[i].co;
    int l = -M, r = M, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1; 
        if (chk(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    } chk(ans); cout << ans * k + sum << '\n';
    //注意最后还得再调用一下求出 sum（否则可能被不不合法的 mid 覆盖） 
    return 0;
}

P5633 最小度限制生成树

这题主要部分跟上一题差不多，主要在于对无解的处理。有两种方法：

第一种是基于这一题来看的。首先要判断 s 连边的个数是否 \ge k。接着先把 s 去掉，那么剩下的点就会形成一些联通块，联通块的个数得 \le k 才能使得 k 条边能使整张图联通。

写的有点丑陋：

int co[N], ts;
bool vis[N], viss[N];
//vis 维护联通块，viss 维护点 
vector <int> p[N];
void dfs(int k) {
    vis[k] = true, co[k] = ts;
    for (auto i : p[k])
        if (!vis[i]) dfs(i);
}
bool chkans() {
    for (int i = 1; i <= m; i++) 
        if (!e[i].f) {
            p[e[i].u].push_back(e[i].v);
            p[e[i].v].push_back(e[i].u);
        } 
    for (int i = 1; i <= n; i++)   
        if (i != id && !vis[i]) ts++, dfs(i);
    memset(vis, 0, sizeof(vis)); int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= m; i++)
        if (e[i].f) {
            if (e[i].u != id) swap(e[i].u, e[i].v);
            if (!vis[co[e[i].v]]) vis[co[e[i].v]] = true, cnt1++;
            if (!viss[e[i].v]) viss[e[i].v] = true, cnt2++;
        } return cnt1 <= k && cnt1 == ts && cnt2 >= k;
}

第二种是利用 wqs 二分的性质。注意到合法的 k 一定在一段区间内（其实联系第一种就很容易得到了），于是对于 \Delta（相当于上文说的二分的斜率，偏移量或许会更直观）分别取 -\infty 和 \infty 得到合法区间，判断 k 是否在其中即可。

这题会卡一点 krusual 快排，需要写上面提到的归并（不能偷懒了，悲）。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
const int M = 3e4 + 5;
inline int read() {
    int w = 1, q = 0; char ch = ' ';
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') w = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
    return w * q;
}
struct node { int u, v, w; bool f;} e1[N], e2[N];
int n, m, m1, m2, id, k, sum, s, fa[N];
inline bool cmp(node x, node y) {
    if (x.w != y.w) return x.w < y.w;
    else return x.f > y.f;
}
inline int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
inline bool chk(int x) {
    for (int i = 1; i <= m1; i++) e1[i].w -= x;
    for (int i = 1; i <= n; i++) fa[i] = i;
    int cnt = 0, n1 = 1, n2 = 1; s = 0, sum = 0;
    for (int i = 1; i <= m; i++) {
        int tx, ty; node t; bool f = 0;
        if (n2 > m2 || n1 <= m1 && cmp(e1[n1], e2[n2])) 
            t = {e1[n1].u, e1[n1].v, e1[n1].w}, f = 1, n1++;
        else t = {e2[n2].u, e2[n2].v, e2[n2].w}, n2++;
        tx = find(t.u), ty = find(t.v);
        if (tx == ty) continue; fa[tx] = ty;
        s += f, cnt++, sum += t.w;
        if (cnt == n - 1) break;
    } for (int i = 1; i <= m1; i++) e1[i].w += x;
    return s >= k;
} 
inline bool chkans() {
    int l, r; chk(-M), l = s; chk(M), r = s;
    return l <= k && k <= r;
}
signed main() {
    n = read(), m = read(), id = read(), k = read();
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        if (u == id || v == id) e1[++m1] = {u, v, w, 1};
        else e2[++m2] = {u, v, w, 0};
    } sort(e1 + 1, e1 + 1 + m1, cmp);
    sort(e2 + 1, e2 + 1 + m2, cmp); 
    if (!chkans()) return cout << "Impossible", 0;
    int l = -M, r = M, ans = -M; bool f = 0;
    while (l <= r) {
        int mid = l + r >> 1; 
        if (chk(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    } chk(ans); cout << ans * k + sum;  return 0;
}

P4983 忘情

wqs 二分优化 dp。

式子太丑了，化简一下 [l,r] 的值就是 (s_r-s_{l-1}+1)^2。设 f_{i,j} 表示前 i 个数分 j 段的最小代价。这个转移一看就很能斜率优化，但优化完也只能做到 O(n^2)。而如果能把第二维砍掉就好了。而 wqs 的条件是凸函数，下面进行不完全证明：

先证明单调递减，用划分成一段的代价和两段进行相减（为了方便，下文是将区间 [l+1,r] 划分成 [l+1,k] 和 [k+1,r]）：

\begin{aligned}\Delta&=(s_r-s_l+1)^2-(s_r-s_k+1)^2-(s_k-s_l+1)^2 \\& = s_r^2+s_l^2+1-2s_rs_l+2s_r-2s_l-(s_r^2+s_k^2+1-2s_rs_k+2s_r-2s_k)-(s_k^2+s_l^2+1-2s_ks_l+2s_k-2s_l)\\&=-2s_k^2+2s_rs_k+s_ks_r-2s_rs_l-1\\&=2(s_r-s_k)(s_k-s_l)-1\end{aligned}

因为 s> 0， 所以 \Delta>1，于是划分更多段一定更优。

同时感性理解（没错，又是它）一下式子的最大值在划分段越少的情况下越小，所以其是满足凸性的。

于是又可以用之前的套路，将 f_n 的求解变得无限制：令 g_x=f_{n,x}-kx，而这个式子的含义其实就是每划分一段可以减小 k 的代价，于是变得和上面的题目一样了，每转移一次减去 k 即可。

这题的边界处理也要注意，由于我们二分出 x\ge m 就返回，所以在斜率优化的时候，要注意在斜率相同的情况下优先选择转移次数多的。这题二分 k 越大，找到的点越大，下界开 -\infty（没有特殊情况开这个就行了），上界由于本身就是单调递减，正常做就能选到 n，所以开 0 就行了。

不讲斜率优化，但这题我写挂了好久。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
const int INF = 1e16;
int n, m, s[N], f[N], cnt[N], X[N], Y[N], q[N];
double cal(int x, int y) { return (Y[y] - Y[x]) * 1.0 / (X[y] - X[x]); }
bool chk(int x) {
    int l = 1, r = 1;
    for (int i = 1; i <= n; i++) {
        int k = 2 * (s[i] + 1);  
        while (r > l && (cal(q[l], q[l + 1]) < k || \
        cal(q[l], q[l + 1]) == k && cnt[q[l + 1]] > cnt[q[l]])) l++;
        //相等优先选择次数多的 
        f[i] = (s[i] - s[q[l]] + 1) * (s[i] - s[q[l]] + 1) + f[q[l]] - x;
        cnt[i] = cnt[q[l]] + 1; X[i] = s[i], Y[i] = s[i] * s[i] + f[i]; 
        while (r > l && (cal(q[r - 1], q[r]) > cal(q[r], i) || \
        cal(q[r - 1], q[r]) == cal(q[r], i) && cnt[q[r]] < cnt[i])) r--; q[++r] = i;
    } return cnt[n] >= m; 
}
signed main() {
    cin >> n >> m;
    for (int i = 1, x; i <= n; i++)
        cin >> x, s[i] = s[i - 1] + x;
    int l = -INF, r = 0, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (chk(mid)) ans = mid, r = mid - 1;
        else l = mid + 1; 
    } chk(ans); cout << f[n] + ans * m << '\n';
    return 0;
}

习题

CF321E Ciel and Gondolas 基本板子，也可以用四边形不等式。

CF739E Gosha is hunting wqs 二分优化 dp，要用到小数二分。

P5308 [COCI2018-2019#4] Akvizna wqs 二分+斜率优化

巨佬的 blog

【学习笔记】WQS二分详解及常见理解误区解释