带权二分(wqs二分) @ Wings            分类 ACM
发布于 星期一, 一月 18 日, 2021 年
更新于 星期四, 八月 5 日, 2021 年

还没理解透彻, 边记着.

在张主席和冯佬的解答下, 应该理解透彻了吧…

适用题型及思路

求贡献和的最值, 但是限制了某个东西必须选恰好$k$个.

没有个数限制很容易做.

把有限制条件的东西带上一个附加一个假想贡献. 也就是说, 选了一个这个东西, 就往我们计算的答案总贡献里加上$\delta$.

$\delta$ 越大, 可能选得的这个东西数量越多/越少.

这样, 我们可以二分$\delta$, 使得恰好选$k$个, 然后贡献里减去我们假想出来的那一部分.

例题: [国家集训队2]Tree I

洛谷

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

边权为整数.题目保证有解.

$n \le 5 \cdot 10^4, m \le 10^5, 1 \le w \le 100$

思路

先这么想:

我们对这棵树进行kruskal, 需要对边按照权值排序. 然而, 仅仅按照权值排序做出来的MST并不是恰好有$need$条白边的生成树. 所以要"打乱排序规则", 让白边更靠前或靠后一点.

如何修改白边的位置呢?

我们还发现, 白边也是取越小的权值的边. 所以, 尝试修改所有白边的权值, 全部加上 $\delta$, 然后做一下MST.

可以发现, 随着 $\delta$ 的增大, 取得的白边数量 $w$ 会减小(非严格), 也就是具有单调性. 所以二分 $\delta$ 就可以解决了.

最后的答案是我们求的MST结果要减去 $w(need) \cdot \delta$

细节

注意到边权是整数, $\delta$ 也应该取整数, 是整数上的二分. 这样就会出现一个问题, $\delta_0$ 时, $w > need$; $\delta_0 + 1$ 时, $w < need$, 没有点能恰好让 $w$ 取到 $need$.

想想为什么会出现这样的情况.

当我们修改一条白边的边权为 $k$ 时, 恰巧有几个黑边的边权也为 $k$, 假如我们的排序是边权相等时优先取白边. 那么这时$w$相对上一个求的$w_{last}$变化就大于1了. 这就是造成不能恰好取到$need$的原因. 权值相等优先取黑边也有同样的问题.

解决方案是: 权值相等优先取白边. 这样二分每个$\delta$对应的$w$中, 取第一个大于等于$need$的$w_1$, 设最后一个小于 $need$的为$w_0$; 如果$w_1 > need$并且$w_0 < need$, 证明存在权值相等的黑边和白边. 此时, 我们只需要将若干条白边换成黑边即可, 这样MST值不变, 但我们在最后算答案的时候要减去的是$need \cdot \delta$(而不是$w \cdot \delta$).

代码
const int MAXN = 1e5+10;
const int WHITE = 0;
const int BLACK = 1;

struct Edge {
	int u, v, w;
	bool operator < (const Edge &E) {
		return w < E.w;
	}
} edges[2][MAXN];
int mm[2];

int n, m, need, ans;

int fa[MAXN];
void init() {
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void uni(int x, int y) {
	fa[find(x)] = find(y);
}

int check(int delta, int &res) {
	init();
	res = 0;
	int w = 0, i = 1, j = 1;
	while (i <= mm[WHITE] && j <= mm[BLACK]) {
		if (edges[WHITE][i].w + delta <= edges[BLACK][j].w) {
			if (find(edges[WHITE][i].u) != find(edges[WHITE][i].v)) {
				w++, res += edges[WHITE][i].w + delta;
				uni(edges[WHITE][i].u, edges[WHITE][i].v);
			}
			i++;
		}
		else {
			if (find(edges[BLACK][j].u) != find(edges[BLACK][j].v)) {
				res += edges[BLACK][j].w;
				uni(edges[BLACK][j].u, edges[BLACK][j].v);
			}
			j++;
		}
	}
	while (i <= mm[WHITE]) {
		if (find(edges[WHITE][i].u) != find(edges[WHITE][i].v)) {
			w++, res += edges[WHITE][i].w + delta;
			uni(edges[WHITE][i].u, edges[WHITE][i].v);
		}
		i++;
	}
	while (j <= mm[BLACK]) {
		if (find(edges[BLACK][j].u) != find(edges[BLACK][j].v)) {
			res += edges[BLACK][j].w;
			uni(edges[BLACK][j].u, edges[BLACK][j].v);
		}
		j++;
	}
	return w;
}

int main() {
	scanf("%d%d%d", &n, &m, &need);
	for (int i = 1; i <= m; i++) {
		int u, v, w, c;
		scanf("%d%d%d%d", &u, &v, &w, &c);
		u++, v++;
		edges[c][++mm[c]] = Edge{u, v, w};
	}
	sort(edges[WHITE]+1, edges[WHITE]+mm[WHITE]+1);
	sort(edges[BLACK]+1, edges[BLACK]+mm[BLACK]+1);
	int l = -101, r = 101;
	while (l <= r) {
		int mid = (l+r) >> 1, sum = 0, w = 0;
		if ((w = check(mid, sum)) >= need) {
			ans = sum - need * mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}

总结

一种套路, 题目符合

  • 求贡献和的最值
  • 限制了某个东西必须选恰好$k$个.
  • 没有个数限制很容易做.
  • 把有限制条件的东西带上一个附加贡献$\delta$, 且$\delta$越大, 可能选得的这个东西数量越多/越少.

就可以直接用.

然后要注意一下选择条件, 选这个东西和不选贡献相等时, 选上, 二分到大于等于$k$的第一个数的答案, 减去 $k\delta$ 即可.

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球
  • 三阶速拧20s

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch