小编use*_*243的帖子

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

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

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

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