DoorKickers的博客

博客

二分图入门好题

2020-03-25 10:47:27 By DoorKickers

题目大意

给定一张有向无环图G, 求最长反链长大小

反链的定义为一个点集S, 其中任意点对(i,j) (ij) 既不存在ij的路径, 也不存在ji的路径

最长反链是|S|最大的的反链

Solution

根据CGL第一零零八六定理

最长反链的大小 = 有向无环图最小路径可重复点覆盖


证明:

我们对G进行传递闭包, 得到的新图记为G

问题转化为证明G的最小路径点覆盖(路径不可重叠)为最长反链的大小

?藏身点集合为H, 路径集合为P, 显然, 每个路径中最多选取一个点, 所以|P||H|

接下来, 尝试构造一种情况使得|P|=|H|

?G2G 的拆点二分图, 对于左侧非匹配点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 ENex=, E is the answer we expected.

else we consider each point p in ENex, move along the path until current point pNex, 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.

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。