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

Question

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

问题是,我们只需要从给定的一组元素中找到不是倍数(可以被b形式整除)的元素的最大数量.如果我们只是从一个元素到它的多个边缘并构造一个图形,那么它将是一个DAG.

现在问题只是改变为找到包含所有顶点的链的最小数量,这些顶点使用Dilworth定理等于antichain基数,因为它是一个部分有序的集合.

使用二分匹配可以找到最小链(如何:它是最小路径覆盖)但现在我无法找到自身的反链元素？

Answer 1

要计算antihain,您可以:

1. 在新的二分图D上计算最大二分匹配(例如,使用最大流算法),当且仅当a除以b时,其具有从LHS a到RHS b的边缘.
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)的顶点之间建立一对一的对应关系.

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