整体二分解决边带双权值的图上问题
缪凌锴_Mathew
·
·
算法·理论
引入
在讲整体二分的日报中，提到如下问题：
给定 n 点 m 边的无向图，边权形如二元组 (x,y)。
一棵生成树的权值是它的边的 \max x+\max y。
求最小生成树。
日报说，维护两个指针，二分其中一维，两个指针的总变化量是 O(n\log n) 的。
什么意思呢？对于 \max x，二分 \max y，\max x 和 \max y 的变化量是 O(n\log n) 的。
设 a_i 为 \max x\le i 时，\max y 的最小值。
显然 a 单调不升，在 x 维上做整体二分。
离散化边权后，可以认为 x,y 都是 O(m) 的。
整体二分
类似决策单调性的分治，整出 $a_{mid}$，左半边 $a$ 值 $\ge a_{mid}$，右半边 $a$ 值 $\le a_{mid}$，对 $a$ 值有个限制。
并查集维护连通情况，分治 $[l,r,L,R]$ 时，并查集内要已经有 $x<l,y\le L$ 的边。
---
### Part 1
枚举 $x$ 在 $[l,mid]$ 内的边 $u\lrarr v$（按 $y$ 从小到大枚举）。
- $y\le L$，并查集连 $u,v$。
- $y>L$，忽略。
---
### Part 2
然后并查集有可能还没连通，需要加一些 $y$ 更大的边。
枚举 $y$ 在 $[L,R]$ 内的边 $u\lrarr v$（按 $y$ 从小到大枚举）。
- $x\le mid$，并查集连 $u,v$，并查集连通整个图时，$a_{mid}=y$。
- $x>mid$，忽略。
---
### 递归前的处理
左边 $L'=a_{mid},R'=R$，右边 $L'=L,R'=a_{mid}$。
需要把 $l\le x\le mid,y\le L'$ 的边存进并查集内，再递归右边。
撤销掉 Part 2 的边，递归右边 $\mathrm{divide}(mid+1,r,L,a_{mid})$。
需要把 $x<l,L\le y\le L'$ 的边存进并查集内，再递归左边。
撤销掉 Part 1 的边，加入 $x<l,L\le y\le a_{mid}$ 的边。
递归左边 $\mathrm{divide}(l,mid-1,a_{mid},R)$。
---
### 复杂度
需要可撤销并查集，时间复杂度 $O(m\log^2 m)$。
同时在撤销栈内的边是 $O(m)$ 的，空间复杂度 $O(m)$。
---
## 例题
### [P7274 草地](https://www.luogu.com.cn/problem/P7274)
转化后就是日报提到的问题。
[record](https://www.luogu.com.cn/record/215621616)
---
### [P4234 最小差值生成树](https://www.luogu.com.cn/problem/P4234)
> 给定 $n$ 点 $m$ 边的无向图，带边权 $w$。
>
> 一棵生成树的权值是它的边的 $\max w-\min w$。
>
> 求最小生成树。
边权看为 $(w,-w)$ 即可。
[record](https://www.luogu.com.cn/record/223337686)
---
### [P2387 [NOI2014] 魔法森林](https://www.luogu.com.cn/problem/P2387)
> 给定 $n$ 点 $m$ 边的无向图，边权形如二元组 $(x,y)$。
>
> 一条路径的权值是它的边的 $\max x+\max y$。
>
> 求 $1$ 到 $n$ 的最短路。
最短路其实也可以二分，因为 $\max x$ 和 $\max y$ 都一定在最短路上，不在最短路上的边不影响答案。
将二分判断改为 $1,n$ 连通即可。
[record](https://www.luogu.com.cn/record/223101949)