P3227 [HNOI2013]切糕 建图证明

· · 题解

注意：本文不是题解，而是正确性证明。

之前想过这个问题，看到确实有很多人像我一样的对正确性有疑问，就写一个详细的证明吧。

大多数本题解法给出了这样一个建图方式：建一条条链，具体，令 (a,b) 为第 a 条链第 b 个点，建有向边：

  1. ((a,b),(a,b+1),cost_{a,b})
  2. (S,(a,1),\infty)
  3. ((a,m),T,\infty)
  4. \forall x,y,z$ ，$x,y$ 相邻，$((x,z),(y,z-D),\infty)

跑最小割，令第 a 个点选了第 b 个位置表现为割了边 ((a,b),(a,b+1))，那么由于第 4 类边，一组合法的割必然满足 |a_i-a_j|\leq D，所以最小割就是答案。

注意到了啥？不加证明的声称了一条链最多割一条边。 为啥是对的？

1. 我们改个建图吧！

加第五类边： ((a,b),(a,b-1),\infty) 即可。显然，在一条链只割一条边的情况下，加了这条边后原来的割依然是割。

注意到这也是题目 P6054 的处理方式。

那道题的限制的种类更加丰富：给 n 个变量 a_i，第 i 个选 j 代价 c_{i,j} 且有若干个 a_{v_i}\geq a_{u_i}+k_i 的限制。

其实，那这道题中，若不存在我们新加的第五类边，则真的有可能最优方案割了两条边。

为啥是对的，首先考虑一个引理：

引理：在割去最小割后，最小割的割边 (u,v) 必须满足 S\to u,v\to T，其中 \to 表示可以到达。

证：若 S\to u ，v\to T 任意一个不成立，不割这条边一定还是个割，且更优。

接下来就简单了，假设最小割有一条链，上面被割了\geq2 条边，那么考虑相邻的两个割边，由于引理，第一个割边右边可以到 T 、第二个左边可以到 S ，那么由于有第五类边，那么无论怎样，S\to T，与是个割矛盾。

2. 本题的特殊性

但本题相比于 P6054 有个特殊的点：D\geq 0

若存在一条链被割两次以上。现基于割掉最小割后的图建一个新图：

对于每条链，若割了若干条边：((a,k_1),(a,k_1+1)),((a,k_2),(a,k_2+1)),\cdots((a,k_t),(a,k_t+1)),

那么，建 t+1 个新点 [a,1],[a,2],\cdots [a,t+1]，代表被割开的一段一段的链。

其中，根据前面所说的引理， [a,2]\cdots,[a,t] 里面都存在点可以从 S 到达，也存在点可以到达 T。

所以对于 [a,2]\cdots,[a,t] 这些新点，对于每个新点 [a,k]，考虑它代表的点的区间所有点 (a,c)，若存在边 ((b,c+D),(a,c),\infty)，且 S\to (b,c+D)。 且 (b,c+D) 在 [b,k'] 里面，那么从 [b,k'] 向 [a,k] 连一条边。

（例如本图中，假设 S\to [b,2] 的最后一个点，那么[b,2] 向 [a,2] 连一条边）

由于 S 可以到达 [a,i] （2\leq i\leq t_a），那么对于新图，必然存在边 ([a,1],[b,i]) （2\leq i\leq t_b）。因为若不存在这样的边，必然所有点都无法从 S 到达。

那么，考虑 ([a,1],[b,i]) 这条边存在导致的问题吧。

由于 D\geq 0，所以边都是向源点方向连的，所以 [b,i] 里第一个可以被 [a,1] 到达的点必然为最左端点。而可以到达最左端点则意味着可以到达所有点，而回顾之前我们说的一定存在一个点可以到达 T，这意味着 S\to T，矛盾。

综上，一定不存在点 [a,i] （2\leq i\leq t_a），也就是每条链必然割一条边。得证。

至于问我为啥 D<0 这个证明就不行了，考虑：

左边的那条虚线边不存在。所以证明无法进行下去。就真的有可能出现两个割边之间，前面一段可以到 T 后面一段可以从 S 到达的合法的两个割边的情况了。

其实根据这个证明不难想到另一种解决 P6054 的方式：手动把缺的那些边补上就好。对于 a_{v_i}\geq a_{u_i}+k_i 的限制，若 k_i>0 那么从 S 开始向 (v_i,1),\cdots (v_i,k_i) 连 \infty 边，把那些缺少的边补上就好。