$\LARGE{引言}$
$wqs$ 二分用于解决一类有恰好选 $k$ 个限制的问题。
通常是优化掉限制这一维。
$\LARGE{Part1.凹凸性}$
设 $f(K)$ 表示恰好选 $K$ 个的限制下的最优解。
凹凸性表示为选的第一次选的数一定是能选的数中最优的。
由于之后的选择会更严格,所以之后选的数一定不必第一次优。
更形式化地说,$\forall 1 \leq i < n , f(i) - f(i - 1) \ge f(i + 1) - f(i)$
上式说明 $f$ 满足上凸性质,即 $f$ 函数斜率递减。
$\LARGE{Part2.如何求切点}$
若已知斜率 $k$ ,那么 $f$ 上对于 $k$ 的切点为将 $y=kx+b$ 中的 $b$ 从 $\infty$ 向下取,第一个卡住直线的点即为切点。
更正式地,切点为函数 $f’(x) = f(x) - kx$ 下的最优解位置 $x$ 。
那么如何求呢?直接算出 $f’(x)$ ,用一些算法(贪心,dp)计算即可。
$\LARGE{Part3.计算答案}$
二分斜率,对应斜率查找切点,若最优解位置 $x$ 在 $K$ 左侧,则调小斜率,否则调大。
$\LARGE{例题}$
$\large{[国家集训队] \textrm{Tree I}}$
给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有 $need$ 条白色边的生成树。
先用黑边做 $MST$ (白边边权为 $inf$),每次添加最小权的白边,然后再删去环上最大的黑边,所以这是一个凸函数。
然后用 $wqs$ 二分套 $kruskal$ 即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10, M = 1e5 + 10;
int n, m, need, sum;
int p[N];
struct Edge {
int u, v, w, c;
} e[M];
bool cmp(Edge a, Edge b) {
if (a.w == b.w) return a.c < b.c;
return a.w < b.w;
}
int find(int u) {
return u == p[u] ? u : p[u] = find(p[u]);
}
int kruskal(int t) {
for (int i = 0; i < m ; i ++ )
if (!e[i].c)
e[i].w += t;
sort(e, e + m, cmp);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int cnt = 0;
sum = 0;
for (int i = 0; i < m; i ++ ) {
int u = e[i].u, v = e[i].v;
if (find(u) == find(v)) continue;
cnt += e[i].c ^ 1, sum += e[i].w;
p[find(u)] = find(v);
}
for (int i = 0; i < m; i ++ )
if (!e[i].c)
e[i].w -= t;
return cnt;
}
int main() {
scanf("%d%d%d", &n, &m, &need);
for (int i = 0; i < m; i ++ ) {
int a, b;
scanf("%d%d%d%d", &a, &b, &e[i].w, &e[i].c);
e[i].u = a + 1, e[i].v = b + 1;
}
int l = -111, r = 111, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (kruskal(mid) >= need) {
ans = sum - need * mid;
l = mid + 1;
} else r = mid - 1;
}
printf("%d\n", ans);
return 0;
}