UOJ Logo r_64的博客

博客

CTSC2008 river

2015-07-27 11:38:42 By r_64

先回顾一下题目吧,给定一个$n$个元素的偏序集(就当是DAG的传递闭包),求:

1)最长反链的长度;

2)一个最长反链;

3)哪些元素可能在最长反链中。

很久以前看到这个题的时候我还没有意识到它就是dilworth定理。。。然后看着题解做了第一问。觉得“第二问好像很水的样子,随便构造就出来了”,可是试了很多种方案都没有构造出来。百度上搜到的blog都是“bzoj上只有第一问的数据,那么我就只做第一问吧”,然后问了一些同学他们也不知道第二问怎么做的样子。某天膜了一下vfk的博客,发现了dilworth定理的一个证明,可惜不是构造性的(就是我不能看着这个证明就构造处一个最长反链)。

最近几天搜到了一个网页

我就抄袭一下这个上面的内容,顺便orz回答这个问题的大爷。。。

回忆一下最小链覆盖的求法。令$n$为偏序集的点数,建立一个二分图,$X$部的$i$号点用$x(i)$表示,$Y$部的$i$号点用$y(i)$表示。对于偏序集中的一条关系$u < v$,在$x(u)$与$y(v)$之间连边。令$m$为二分图的最大匹配的大小。则答案为$n-m$。

构出了二分图之后我们可以构出其最大独立集$I$(怎么构的话英文wiki和上面的网页上都有吧)。对于一个$1\le i\le n$,如果$x(i)\in I$且$y(i)\in I$,那么将$i$加入我们的反链$A$。

首先我们证明$A$的确是个反链。否则的话假设$u\in A,v\in A,u < v$。那么应该存在$x(u)$到$y(v)$的边。而$x(u),y(v)$却是在同一个独立集中的。所以产生矛盾,$A$是反链。

然后我们证明这个反链的大小至少为$n-m$。把独立集中的点称作黑点,其他点称作白点。那么黑点的数目是$2n-m$。而黑点的数目=$|A|$+(满足$x(i)\in I$或$y(i)\in I$的$i$的数目),后者不会超过$n$,则前者至少是$n-m$。

这样!我们构造出了一个大小至少是$n-m$的反链!然后最小链覆盖的大小就是$n-m$,反链的大小不会超过它,所以这个反链的大小就是$n-m$,且是我们要求的最大反链。

鼓掌熊

数据、某蒟蒻写的spj、某蒟蒻写的程序 提取密码:tjqs(好像不需要提取密码)

spj可以直接用于lemon。

如果发现程序或spj有错请在下方评论或私信r_64。

评论

z123z123d
膜r_64
00ffcc
orz
Yxs
orz

发表评论

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