浅谈双极定向及其应用

[wiki链接](https://en.wikipedia.org/wiki/Bipolar_orientation) 双极定向是说，给定一张无向图，要求给每一条边确定一个方向，使得原无向图成为一个DAG，并且恰有一个入度为0的点 $S$ 和一个出度为0的点 $T$。wiki中似乎将这样的 $S$/$T$ 称呼为 source/sink。 显然不是所有图都有合法的双极定向。 # 例题——CC CUREK [原题链接](https://www.codechef.com/MAY19A/problems/CUREK) ## 题目大意 给你一张 $n$ 个点 $m$ 条边的无向连通图，保证不存在重边和自环。 这张图的每个点都是白色的，你想要把它们全都染成黑色。刚开始你可以选择一些点把它们染成黑色，并需要付出这些点权值之和的代价；接下来你每次可以选择一个和黑点相邻的白点，并把它染成黑色。你还需要保证在每一步操作（包括最开始染那些点）之后，所有白点的导出子图连通。 请你最小化你所需要付出的代价，并构造一组代价最小时的方案。 # 做法 ## 算法1 考虑树上怎么做。 首先，最多只能剩一个叶子在最开始没选，否则在染到另一个叶子的父亲时白点会不连通。 我们把点权最大的那个叶子提根，剩下每个叶子都必须在最开始被选。构方案只需要不断剥叶子即可，可以保证始终连通。 ## 算法2 我们从树上的做法得到启发，猜想对原图建出点双树后，只有一个叶子点双最开始没有被选，同时这个叶子是所有叶子中最小权值最大的。 ### 引理1 > 对于一组初始黑点的方案，满足所有白点初始均连通。则该初始方案合法，当且仅当所有白点构成的点双树上，至多只有一个叶子点双，使得其中的白点不与任何黑点相连通。 引理的必要性是显然的，跟树的情况类似证明即可。对于充分性，我们尝试对白点数量归纳并构造证明。 跟树的情况一样，我们仍然将不与所有黑点相邻的叶子点双提根，之后不断剥剩下的叶子。这样我们唯一需要实现的问题是，在一个点双内给定最开始被染黑的点（只有一个）、需要在最后一个才被染黑的点，求一组合法方案使得它满足题目中所描述的条件。 对于这个问题，每一步如果某个点染黑之后白点仍然连通，这一步就选择染黑该点。证明是简单的，我们考虑新黑点所属的点双，在该点染黑后，原点双分裂成的子点双一定摆成一条链。于是唯一可能新产生的叶子点双，必为链的两端，与新黑点相邻。这样就递归到了白点更少的子问题。 从而引理得证。 直接模拟上述做法，对于每一轮，我们跑出白点导出子图中所有的割点，那么割点就是不能剥的，非割点就是能剥的。复杂度 $O(n^2)$。 ## 算法3 尝试直接优化算法2，发现我们实际上要操作的是删边维护割点。使用维护动态图双连通性的相关算法即可。 复杂度 $o(n^2)$。 ## 算法4 根据前述分析，我们只需考虑原图是点双连通分量的情况，不过这时相对于原问题，会要求染黑的第一个点 $S$ 和最后一个点 $T$ 均固定。 我们尝试递归求解这个问题，但在这之前我们先思考一下有哪些递归手段。 记原图为 $G$。 * 如果 $G'$ 为 $G$ 删掉一条边得到的图，则 $G'$ 的合法删点顺序对 $G$ 也是合法的。 * 对于一个二度点 $x$，记其邻居为 $y,z$。对于任意 $G'$ 的合法删点序列 $a$，由对称性不妨设 $y$ 在 $a$中比 $z$ 更靠前，则我们在 $a$ 中 $y$ 的位置后面插入 $x$，即可将 $a$ 改进为图 $G$ 的解。 实际上只靠删边和缩二度点这两种递归手段，足以处理任意点双连通图。 具体的，我们先找出整张图的一棵生成树，然后对于每个叶子，我们保留它最浅的一条返祖边，注意这不改变点双连通性。 这样，每个叶子就都变成了二度点，我们就可以删除所有叶子啦！ 如此不断操作下去，整张图就可以变为一条以 $S$ 和 $T$ 为两端点的链。此时合法删点序列的求解是平凡的，还原为原图的解序列也是容易的。 最后总复杂度$O(n)$。 应该说这里的构造过程跟 [Ear_decomposition](https://en.wikipedia.org/wiki/Ear_decomposition) 有点像。 实际上到这里我们已经将双极定向的存在条件以及线性构造方法分析清楚了。下面是一些其它相关题目。 # 相关题目1——CF1192F [题目链接](https://www.luogu.com.cn/problem/CF1192A) 可以发现本题题目描述跟上一道题很像，不过细节上有些差异，诸如在两条约束中一个形式是八连通，另一个是四连通；还有多了字典序的要求。 ## 这题和上一题有什么相关性？ 先考虑**从后往前**逐位构造合法解，仿照上一题，我们直接猜想，每一步任选一个与无穷远处四连通的，且删掉后剩下点集仍然八连通的点，都是合法的。 实际上这个命题是对的。只是由于一些不对称性，证明的时候需要不同的处理。 首先将命题形式改造为任一八连通图点集都存在这样的点，并且有 $min(2,点集大小)$ 个合法点。之后我们对点集大小进行归纳。取所有点中最左下方点 $u$，如果这是一个割点，则去掉该点后全集恰划分为两八连通点集 $A,B$，并且 $A,B$ 一定不会出现一个把另一个包在内部的情况——因为 $u$ 向右上方至多连出去四条边。于是由归纳假设，$A \cup \{u\}$ 和 $B \cup \{u\}$ 一定分别包含一个不等于 $u$ 的合法点，且其也是原点集的合法点。对于最右上方的点 $v$ 施以同样处理。如果 $u,v$ 均非割点，则 $u,v$ 已构成两合法点。从而命题得证。 ~~平凡讨论有点多，您也可以选择跳过或者看官方sol。~~ ## 后续做法 回到原题，问题核心变为如何即时维护所有非割点集合。关于字典序的要求是简单的，只需将存储合法点的容器换成优先队列即可。 注意到**八连通意义下的割点是个局部的性质(“so the information about articulation-ness of cells is local”)**。 ~~于是修改时我们只需对周围 $O(1)$ 个点，检查其各自邻居的连通情况即可~~ 稍微提一下细节，首先八连通的对偶是四连通，然后只需考虑上下左右四个点中同属于一个连通块的白点。 可以发现最后产生影响的一定是白点对（而不是三元组）。 然后只需考虑被检查的点删除后，配合枚举的白点对，能否产生一组割即可。您可以自行手画一下来加以理解。 具体实现的时候，需要维护两个白点是否属于同一个白四连通块。 最开始先跑一遍floodfill标记每个白点所属连通块的颜色，需要手动添加一些辅助白点。 由于修改操作只有黑变白，所以每次从新增的白点开始，暴力标记新产生的与无穷远处连通的白点即可。 # 相关题目2——IOI2019景点划分 [题目链接](https://loj.ac/p/3176) 首先令 $a \le b \le c$，我们只需求出两连通点集 $A,B$ 使得 $|A|=a,|B|=b$。 考虑对原图建立圆方树，圆点表示割点，方点代表点双。圆点的权重设为1，方点的权重设为点双中的非割点数量。 显然至多只有一个点双 $C$，满足 $A \cap C$ 与 $B \cap C$ 均不为空，否则连接两点双的路径上的割点会导出矛盾。 我们枚举这个点双 $C$ 在圆方树上的方点 $u$。 将 $u$ 提根，如果 $u$ 最大的一个子树大于 $n-a$ 了，则从 $C$ 必然无法导出合法解。 否则，如果 $u$ 最大的子树大于等于 $b$，则在该子树内部任选 $b$ 个点，外部任选 $a$ 个，即得合法解。 最后一种情况，我们需要将点双 $C$ 进行拆分。考虑利用CUREK一题中的构造，我们可以得到 $C$ 中点的一个排列 $p$，使得其所有前缀与所有后缀均构成连通点集。 设 $C$ 中一个割点的权为其在圆方树上的子树大小（以 $u$ 为根），一个非割点的权为1。我们截取 $p$ 的第一个权和不小于 $a$ 的前缀，则该前缀的权和一定不超过 $a+b$——因为最大子树不超过 $b$。于是对应后缀的权和一定不小于 $b$，否则 $a+b+b \gt n$ 矛盾了。可以发现这样的前后缀切分方案导出了一组合法的原图点集划分方案。 并且这样枚举 $C$ 显然是充要的，最后总复杂度为 $O(n)$。 这是一份[参考代码](https://loj.ac/s/601526)，一些实现细节和文中叙述有差异。 感觉在有CUREK一题作为模板的情况下思维量比官方做法小好多，不过得现写CUREK的话就有点大力飞砖了，这玩意还是有点难写的。 IOI19我场外围观直播的时候，还以为64分是给想到了CUREK但只会 $O(n^2)$ 构造的。出来后听说64分是随机，感觉大跌眼界。 可惜我永远也没有坐在IOI赛场里的机会了，狂笑.jpg