感觉是一个很神秘的东西。
例题
P2619 [国家集训队] Tree I
- 从 \(m\) 条边中选 \(n-1\) 条
- 要求选恰好 \(k\) 条白边，且边集是原图生成树
- 求边权和的最小值
这题不算是 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，要用到小数二分。