最长反链长

发表于 分类于 阅读次数：

去年写过的东西加点补充就算做今天写的了

基本概念

首先得知道链和反链是什么。

在 有向无环图（ DAG ） 中，
链是满足任意两点 x, y 要么 x 可以到达 y 要么 y 可以到达 x 的点集 （即使只有一个点），
反链是任意两点没有路径的 点集 。

那么最长反链，就是点的个数最多的反链。

定理

不加证明地丢出两个定理：

  1. 最长反链长度 = 最小链覆盖（用最少的链覆盖所有顶点）
  2. 最长链长度 = 最小反链覆盖（用最少的反链覆盖所有顶点）

那么要求的其实是最小链覆盖。

不相交

假设最小链覆盖不会相交，怎么求出这个最小链覆盖？

把每个点 i 拆成 i1 和 i2 ，考虑建立二分图。
如果存在一条边 (x, y) ，那么就在二分图中建立 (x1, y2) 的边。
这样建立二分图之后，原图的点数 - 二分图最大匹配 = 原图的最小链覆盖
（链不相交）。

这样为什么是对的呢？
一个点也可以看作是一个链，因此可以将每个点独立来看做初始状态。
然后每次在二分图中选出一条边，就是将两条链连接成一条链，
使用的链数就减少一个。

而链不会相交，所以在二分图中选出的边也是不相交的，也就是二分图的最大匹配。

栗子

如果链可以相交呢？

举个栗子：

1
2
3
4
5
5 4 // 五个点四条边
1 3 // 1 连向 3
2 3 // 2 连向 3
3 4 // 3 连向 4
3 5 // 3 连向 5

这里不相交的最小链覆盖是 3 ，而实际的最小链覆盖是 2 。

观察不相交的最小链覆盖 {1-3-5, 2, 4} 与最小链覆盖 {1-3-5, 2-3-4} 。

发现由于不能相交， 1-3-5 这条链把 2-3-4 这条链切断了，
分成 2 和 4 两条链，因此比最小链覆盖多了一条链。

如果可以让 2 跨过 1-3-5 与 4 相连呢？

相交

将原图做一次 Floyd ，
之后就可以知道任意两点 x, y ，x 是否能到达 y 。

把建立二分图的方法改造了一下，只要 x 能到达 y ，
就直接连一条边 (x, y)，这样就可以“跨过”其它链来连接两条链了。

这个时候，原图最长反链长度 = 最小链覆盖 = 原图点数 - 二分图最大匹配。

方案

《 [CTSC2008] 祭祀》一题中需要具体地求出一组最长反链方案。

对于上述的二分图，考虑求出其任意一组最大独立集，那么所有满足 x1 和 x2 都在最大独立集中的点 x 就构成了原图的一组最长反链。

由于最大独立集和最小点覆盖互为补集，问题就是要在二分图上求一组最小点覆盖。

从一组可行的点覆盖开始增广，最初的一组可行的点覆盖就是二分图左边的点的集合。

先求出一组最大匹配。然后从左边所有非匹配点沿非匹配边 - 匹配边 - 非匹配边 - 匹配边开始 dfs ，也就是找増广路，但事实上最大 匹配是不存在増广路的，因此 dfs 出来的路径只能是“伪増广路”，然后标记所有“伪増广路”到达过的点。注意到一条“伪増广路”一定包含 奇数个点，并且左边的点数比右边的点数多一，那么把所有被标记的左边的点删掉，把所有被标记的右边的点加上，每一条“伪増广路”都 会使得当前点覆盖的大小尽可能变小，事实上这样最终就能得到一组最小点覆盖。

严格的证明的话，利用最小点覆盖 = 最大匹配的这个条件，分别证明其是最小的以及是点覆盖即可，略。

祭祀还要求所有最长反链的并，也就是要对于每个点判断其是否存在于任意一组最长反链中，钦定之重新求最长反链，如果重新求出来的 最长反链长恰为原图最长反链长就说明该点存在于一组最长反链中。

（这玩意不画图一点都不直观）