algorithm - 如何获得 SPOJ-DIVREL 中的反链元素？

Question

问题：http ://www.spoj.com/problems/DIVREL

有问题的是，我们只需要从给定的一组元素中找到最大数量的元素不是倍数（a 可以被 b 整除）。如果我们只是从一个元素到它的倍数创建一条边并构建一个图，它将是一个 DAG。

现在问题变成了使用Dilworth 定理找到包含等于反链基数的所有顶点的最小链数，因为它是一个部分有序的集合。

可以使用二分匹配找到最小链（如何：它是最小路径覆盖）但现在我无法找到反链元素本身？

Answer 1

要计算反链，您可以：

1. 当且仅当 a 整除 b 时，计算具有从 LHS a 到 RHS b 的边的新二分图 D 上的最大二分匹配（例如，使用最大流算法）。
2. 使用匹配来计算最小顶点覆盖（例如，使用Konig 定理证明中描述的算法
3. 反链由不在顶点覆盖中的所有顶点给出

两个这样的元素之间不能有边，否则我们会发现一条边没有被顶点覆盖，从而导致矛盾。

找到最小顶点覆盖的算法是（来自上面的链接）：

1. 令 S0 由 M 不匹配的所有顶点组成。
2. 对于整数 j ≥ 0，令 S(2j+1) 是所有顶点 v 的集合，使得 v 通过 E\M 中的某个边与 S(2j) 中的一个顶点相邻，并且 v 没有包含在任何先前-定义集合 Sk，其中 k < 2j+1。如果不存在这样的顶点，但仍有未包含在任何先前定义的集合 Sk 中的顶点，则任意选择其中一个并使 S(2j+1) 由该单个顶点组成。
3. 对于整数 j ≥ 1，令 S(2j) 是所有顶点 u 的集合，使得 u 通过 M 中的某个边与 S(2j-1) 中的顶点相邻。请注意，对于 S(2j-1) 中的每个 v，都有一个与之匹配的顶点 u，否则 v 将在 S0 中。因此 M 建立了 S(2j-1) 的顶点和 S(2j) 的顶点之间的一一对应关系。

奇数索引子集的并集是顶点覆盖。