题目大意
给定一张有向无环图G, 求最长反链长大小
反链的定义为一个点集S, 其中任意点对(i,j) (i≠j) 既不存在i到j的路径, 也不存在j到i的路径
最长反链是|S|最大的的反链
Solution
根据CGL第一零零八六定理
最长反链的大小 = 有向无环图最小路径可重复点覆盖
证明:
我们对G进行传递闭包, 得到的新图记为G′
问题转化为证明G′的最小路径点覆盖(路径不可重叠)为最长反链的大小
?藏身点集合为H, 路径集合为P, 显然, 每个路径中最多选取一个点, 所以|P|≥|H|
接下来, 尝试构造一种情况使得|P|=|H|
?G′2 为G′ 的拆点二分图, 对于左侧非匹配点xout, 说明这个点是路径的终点, 反复横跳后找到该路径的起点
?E to denote that the set of the end point. For each of them, we label all the point that current point can arrive, and denote as Nex.
If E⋂Nex=∅, E is the answer we expected.
else we consider each point p in E⋂Nex, move along the path until current point p′∉Nex, then remove p from E and add p′ to E.
and repeat with new E until the condition is satisfied.
We can prove that we can find a legal p′ in any time when the condition is not satisfied.
Assumed that we can not find that p′, there must exsit a point q that can arrive whole path where includes p. And it also means that the P is not satisfied with the minimality which contradict with the premise.