【学习笔记】带权二分

本文主要是介绍【学习笔记】带权二分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

直线与凸壳的相切关系

如果凸壳的斜率互不相同，凸壳上存在两点间的斜率是 $k$ ，那么斜率为 $k$ 的直线和凸壳有两个切点（如果存在相同的斜率那么可能切更多的点）,如果不存在，则只有一个切点。

令红线的斜率为 $k_1$ , 蓝线的斜率为 $k_2$ 有且仅有 $k\in [k_1,k_2]$ 的斜率能够切到绿点。

带权二分的基本原理与应用范围

带权二分一般解决的是形如这样的问题：

给定 $n$ 个物品，要求从中恰好选出 $m$ 个，满足某种限制，要求最大化收益 / 最小化价值，且如果不限定数目问题比较简单。

令 $g(i)$ 为选出恰好 $i$ 个物品的最大化收益，满足于函数 $(i,g(i))$ 是凸壳。

下面以上凸包（从左到右斜率递减）为例子。

我们的目标是求出 $g(m)$ 。

做法是，二分一个斜率$k$，然后找到斜率为 $k$ 的切这个凸壳的直线切于哪一点。

可以发现，随着 $k$ 的减小，这条直线切的点会越来越靠右，就像这样：

于是我们二分 $k$ 直到这条直线与凸壳的切点为 $(m,g(m))$ 。

问题变成了：当二分出一个 $k$ 时，怎么求被切的点是谁。

可以发现，所有斜率为 $k$ 且与凸壳有交点的直线中，截距最大的那一条直线，就是与凸壳相切的直线。

设直线 $y=kx+b$ 与凸壳 $g(x)$ 交于点 $(i,g(i))$ ，那么有方程 $ki+b=g(i)$ ，移项：

\[b=g(i)-ki \]

考虑 $g(i)-ki$ 的组合意义：$g(i)$ 表示选恰好 $i$ 个的最大化收益，那么 $g(i)-ki$ 等价于每个物品价值 $-k$ 后选恰好 $i$ 个的最大化收益。

那么 $b$ 就等价于所有物品价值 $-k$ 后，没有数量限制的最大化收益。最优解取到的个数 $i$ 即与凸壳交点的横坐标。

带权二分的细节与边界

如何确定实数二分与整数二分

若函数的定义域以及凸壳斜率（凸壳相邻两点连线的斜率，即凸壳上相邻两点的差分除以间距）都取在整数上一般来说整数二分就好。

因为一定存在一个整数斜率k满足切点之一是 $m $（存在一个 $m$ 与相邻点之间的斜率与 $k$ 相同）。

如何确定二分边界

令 $\Delta$ 为凸壳相邻两点函数值的能取到的最大差分，那么二分边界为 $[-\Delta,+\Delta]$ 。

例题

P2619 [国家集训队]Tree I

题目描述

给你一个无向带权连通图，每条边是黑色或白色。

让你求一棵最小权的恰好有 $need$ 条白色边的生成树。题目保证有解。

数据范围

$V\le 5\times 10^4,E\le 10^5$ ，边权均为 $[1,100]$ 中的整数。

题解

分黑白考虑。
如果两点之间没有黑边，我们假设连了一条权值为$ +\infty$ 的黑边。
找出黑边形成的最小生成树。
每次加入一条最小的白边，删除一条可以删的最大的黑边，所以也具有凸性质。

排序要优先把白边排到前面，这样我们最后求得的是切到的最靠右 $x$ 最大的点。

P5633 最小度限制生成树

题目描述

给你一个有 $n$ 个节点，$m$ 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 $s$ 的节点正好连了 $k$ 条边。

不保证有解。

数据范围

$1\le n\le 5\times 10^4,1\le m\le 5\times 10^5,1\le k\le 100,0\le w\le 3\times 10^4$ 。

题解

发现题意与上题本质相同，我们将所有与点 $s$ 相连的边染成白色，其他边染成黑色。

问题等价于求一棵最小权的恰好有 $k$ 条边的生成树。

注意到，本题 不保证有解 。

在上一题的题解没有着重讨论整数二分的实现细节与正确性。

首先我们需要证明：凸壳的定义域为 $[l,r]\cap Z$ 即定义域是连续的一段整数区间。

对于这一性质的证明并不困难，任意一棵包含 $i$ 条白边的生成树都可以看成包含 $i-1$ 条白边的生成树使用一条非树边（白边）替换一条生成树中的黑边。因此，凸壳的定义域一定是连续的一段整数区间。

那么凸壳上的斜率，均为正整数，因此可以直接在整数上二分。

对于判是否有解相当于判 $k$ 是否在凸壳的定义域内。

而对于整数二分，每次 $\text{check}$ 的时，排序要优先把白边排到前面，这样我们最后求得的是切到的最靠右 $x$ 最大的点。

那么我们最后二分出来的斜率，就是 **切到的最靠右的点大于等于 $k$ ** 的最小的斜率。

因为切到固定的点的斜率是上下界是能够确定的，所以对于凸壳定义域内的点 $p\in (l,r]$ ，二分出来的斜率一定是 $g(p)-g(p-1)$ ，如果 $k$ 在值域内二分出来的值域一定也是 $g(k)-g(k-1)$ ，这个斜率能够切到的最右点就是我们 $\text{kruskal}$ 函数返回的答案。

std::pair<int,int> kruskal(int k) {
	std::vector<edges> e; int l0 = 0,l1 = 0;
	for (int i = 0; i < m; i++) {
		if (l1 >= edge[1].size()) {
			e.push_back(edge[0][l0]); e[i].val -= k; ++l0; continue;
		}
		if (l0 >= edge[0].size() || edge[1][l1].val < edge[0][l0].val - k) {
			e.push_back(edge[1][l1]); ++l1;
		} else {
			e.push_back(edge[0][l0]); e[i].val -= k; ++l0;
		}
	} int cnt = 0,ans = 0; rep(i,1,n) fa[i] = i;
	for (int i = 0; i < e.size(); i++) {
		if (get(e[i].u) == get(e[i].v)) continue;
		merge(e[i].u,e[i].v); ans += e[i].val; 
		if(e[i].col == 0) ++cnt;
	} 
	return {cnt,ans};
}

如果二分出来的斜率能够切到的最右点恰好等于 $k$ ，那么 $k$ 一定在凸壳的定义域内。

如果二分出来的斜率能够切到的最右点在 $k$ 左边，显然 $k$ 一定不在凸壳的定义域内。

如果二分出来的斜率能够切到的最右点在 $k$ 右边，那么我们需要判断这条直线能不能切到 $k$ 点。

这里我们采用组合意义判定：

斜率 $p$ 能够切到点 $k$ 当且仅当存在一棵包括 $k$ 条边的生成树，满足边权和恰好为 kruskal(p).second 。

bool check(int k,int val) {
	std::vector<edges> e; int l0 = 0,l1 = 0;
	for (int i = 0; i < m; i++) {
		if (l1 >= edge[1].size()) {
			e.push_back(edge[0][l0]); e[i].val -= k; ++l0; continue;
		}
		if (l0 >= edge[0].size() || edge[1][l1].val < edge[0][l0].val - k) {
			e.push_back(edge[1][l1]); ++l1;
		} else {
			e.push_back(edge[0][l0]); e[i].val -= k; ++l0;
		}
	} int cnt = 0,ans = 0; rep(i,1,n) fa[i] = i;
	for (int i = 0; i < e.size(); i++) {
		if (get(e[i].u) == get(e[i].v)) continue;
		if (cnt == need && e[i].col == 0) continue;
		merge(e[i].u,e[i].v); ans += e[i].val; 
		if(e[i].col == 0) ++cnt;
	} 
	int cc = 0;
	rep(i,1,n) if (fa[i] == i) ++ cc;
	if (cc > 1) return false;
	if (ans != val) return false;
	return true;
}

P4767 [IOI2000]邮局

题目描述

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

数据范围

$1\le P\le 300,P\le V\le 3000$

题解（四边形不等式证明待填！）

首先，将所有村庄的坐标排序。

我们考虑固定每个邮局的位置为 $pos[1],pos[2]...pos[P]$ 。

可以发现，每个邮局 “分管” 一段连续的区间，该段区间内的村庄对答案的贡献均为村庄与该邮局的距离。

对于这个问题有两种 DP 方式：

一种是考虑枚举最后一个邮局的位置。令 $f[i][j][0/1]$ 为考虑前 $i$ 个村庄，建 $j$ 个邮局且第 $i$ 个村庄不建 / 建邮局的最小花费。
一种是考虑枚举每个邮局 “分管” 的区间（间接枚举邮局的放置位置），令 $f[i][j]$ 为考虑前 $i$ 个村庄，建 $j$ 个邮局的最小花费。 $w(l,r)$ 为在 $[l,r]$ 的村庄建一个邮局，区间 $[l,r]$ 内部村庄的最小花费。转移枚举最后一段 “分管” 区间即可。

其中后者转移的复杂度是不受值域的限制的且转移较为简单。

经过打表发现，$i\in [1,n]\cap Z,(i,f[n][i])$ 构成的点集是下凸壳。

而如果没有钦定数量的限制，第二种 DP 可以优化到 $O(n^2)$ 的复杂度。

因为 $m$ 一定在凸壳的定义域上，且凸壳中的斜率均为整数，直接在整数上带权二分即可。

对于凸壳的证明似乎要四边形不等式。待填！

这篇关于【学习笔记】带权二分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程