P4298 [CTSC2008] 祭祀 题解

· · 题解

一种可能更优秀的做法，来自 @kradcigam。

约定

给定一个有源汇网络，对于任意流函数 f，满足如下限制：

  1. 容量限制：f(u,v)\le c(u,v)；
  2. 流量平衡：除去 s,t 以外 f(u)=\sum_v f(u,v)=0；
  3. 反对称性：f(u,v)=-f(v,u)

称这个流的流量为 |f|，显然有 f(s)=-f(t)=|f|。

割 \set{S,T} 的权值记为 ||S,T||。

残量网络是一个新的网络 G_f，满足 c_f(u,v)=c(u,v)-f(u,v)。

最小割的方案

首先我们研究全体最小割方案的形态。

结论 1. 任取流函数 f 以及割 \set{S,T}，有 \sum_{x\in S,y\in T} f(x,y)=|f|。

证明。显然有 f(s)=\sum_{x\in S} f(x)=\sum_{x\in S,y\in T} f(x,y)。

由此可以得到对于任意流 f 和割 \set{S,T}，有 |f|\le ||S,T||。

结论 2. 一个割 \set{S,T} 是最小割，当且仅当存在最大流 f，有 \forall_{x\in S,y\in T}\ c_f(x,y)=0。

证明。若存在 c_f(x,y)\ne 0，则根据结论 1 有 |f|<||S,T||，与最大流最小割定理矛盾。

并且注意到这一性质若对于某个最大流成立当且仅当其对于所有最大流成立。总之我们得到了有关最小割的三个两两等价的命题。

所以我们现在可以如此描述所有合法的最小割：任取最大流 f，全体合法的最小割等价于残量网络 G_f 上全体大小为 0 的割。

求解本题第三问

前置知识：最大权闭合子图。

首先我们对本题采用最大权闭合子图的转化：对每个点拆成 (u_0,u_1)，其点权分别为 -1 和 1，入边全部改到 u_0，出边改到 u_1，然后求最大权闭合子图。

此时所有 u_1 被选且 u_0 未被选的点就是一组最长反链。

这里我们最大权闭合子图采用左部点为正权，右部点为负权的建模。

所以，要求解该点是否可以被选，则等价于求最大权闭合子图上，是否存在一组最小割，满足 u_0\in T,u_1\in S。

将其转化到残量网络上大小为 0 的割，则相当于问残量网络上 u_1 能否走 c_f(u,v)>0 的边到 u_0，若能则这个点不能被选。

由于 u_0 显然总是能到 u_1，这等价于这两个点在 G_f 上属于一个强连通分量。可以在求出残量网络后 O(n+m) 解决。

需要注意的是，需要先考虑 u_0 是否和 S 在同一个强连通分量，若是的话显然没有割使得 u_0\in T，u_1 同理。

求解最小字典序答案

接下来所说的图都是由 c_f(u,v)>0 的边组成的图。

先对此图缩点。现在把 s 能到达的点以及能到达 t 的点在最小割中的归属已经确定，标记它们。

从小到大枚举每个点，如果 可以令 u_0 \in S,u_1 \in T 并且不违反已有的标记，并且两个点不在一个强连通分量，则把这个点加入答案，然后把 u_0 可达的点标记为 S，把可达 u_1 的点标记为 T；否则我们直接跳过这个点，显然此时不关心这两个点最终在最小割中的位置。

复杂度也是 O(n+m)。

现在整个问题需要求出任意一组最大流，之后的部分都是线性。我不会将此题上的最大流分析到优于 O(nm) 的复杂度，如果有大手子会分析请私信！！！