WQS二分

解决一类要求选择特定数量的某种物品前提下的最优化问题。

P2619 [国家集训队] Tree I

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 $m$ 条白色边的生成树。

设 $g(i)$ 是选 $i$ 条白色边的最小生成树。

则 $(i,g(i))$ 形成一个下凸包。

简易证明：若选 $x$ 条白色边恰好得到最小生成树，则每限制必须多选一条或者少选一条都会令代价增加。

若不限制数量，则是一个简单的最小生成树。

看见凸包则联想到线性规划，能否将问题转化成给定斜率求最小截距的问题？

不妨设每选择一条白色边，就要多花费 $x$ 点代价，则新的总代价是 $f(i)=g(i)+i\times x$

转化一下 $g(i)=-i\times x+f(i)$

从几何角度看这个等于是一条过点 $(i,g(i))$ ，斜率为 $-x$ 的直线。

如果要截距 $f(i)$ 最小，在下凸包的范围内，肯定要切着下凸包的端点。

在这个基础上（每选择一条白色边，就要多花费 $x$ 点代价），只要做普通的最小生成树，顺便记录一下一共选了几条白色边，就可以得到最小截距 $f(i)$ 和边数 $i$ 了。

但是 $i$ 可能不等于 $m$ ，怎么办呢，可以进行调整。

从图上可以看出：

如果 $i<m$ ，想要让相切的点向右移动，那么应该增大斜率

如果 $i>m$ ，想要让相切的点向右移动，那么应该减小斜率

将这个斜率 $x$ 直接二分，然后根据每次选出的最小生成树的白色边数调整二分的范围。

最后由得到的 $g(m)=f(m)-m\times x$ 得到真实答案

特殊情况：

注意这里，有可能存在并不能二分出一个斜率，让选中的边数恰好等于 $m$。

比如这个斜率会同时和几个点相切，假设中间那个点是 $m$ ，那么最小生成树求得的白边数量可能是 $m-1,m,m+1$。

如果你斜率恰好取到这个值，然后发现边的数量是 $m+1$ ，此时你把斜率减小，就会发现切不到 $i=m$ 了。

而如果你此时选出的边的数量是 $m-1$ ，把斜率增大，又会发现也切不到 $i=m$ 了。

最小生成树得到的边数不是 $m$ ，但是这个斜率既不能减小，也不能增大，否则都会错过正确答案，这怎么办呢。

针对这道题目，解决办法是当边的权值相同时，优先选择白色的边

当一个斜率切很多点时，会默认选择横坐标最大的位置上（这里是 $i=m+1$）

然后每当得到的 $i\ge m$ 时，就将斜率记录下来，作为答案。

while(l<=r)
{
	if(check(mid)>=m) ans=mid,r=mid-1;
    else l=mid+1;
}

这样如果，当斜率同时切到 $m\sim m+k$ 时，即使再减小斜率，答案也已经记下来了，之后因为不会产生 $\ge m$ 的结果，所以此时就是最终答案。

当然这样最后得到的结果也不是减去 $i\times m$ 了，而是看具体选了几条白边。

这是下凸包的情况，如果是上凸包，你又优先选择了有数量规定的物品，因为上凸包横坐标左移是要斜率增大的，所以应该变成：

while(l<=r)
{
	if(check(mid)>=m) ans=mid,l=mid+1;
    else r=mid-1;
}

这个要根据你二分的写法来定，希望能完全理解凸包、切点和斜率的关系才不会错。

如果自己搞不清楚也可以记下来：

1、权值相同优先选有数量规定的物品

2、当选择的数量 $>=$ 规定数量时记录答案

3、如果是下凸包，$>=$ 时斜率减小

4、如果是上凸包，$>=$ 时斜率增大

当然还是希望你能完全理解其中含义。

总结：若问题根据物品选择的数量形成上凸包或者下凸包，当不限制数量时很好解决，就可以使用 $wqs$ 二分。

练习题

跳石头，搭梯子

Gosha is hunting

P4983 忘情