BZOJ 1143 [CTSC2008] 祭祀 river

发布于 2017-06-12  283 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1143

题意:在一个 DAG 上选若干点,使得点两两不互达。


据说原题需要输出方案 但是这里不需要(需要也不会 qwq
题意即为求一个 DAG 的最长反链

链:一个点集,对于点集中的点 u,v,要么 u 能到 v,要么 v 能到 u
反链:一个点集,对于点集中的点 u,v,互相不可达
最长链:一个图中的链点数最多的那个
最长反链:一个图的反链点数最多的那个

Dliworth 定理:最长反链长度 = 最小链覆盖数

这里 有很棒的证明, 有空(挖坑)会自己证一遍

最小链覆盖=可重点最小路径覆盖

可重点最小路径覆盖怎么搞呢? 对原图判断两点连通性后等于不可重点最小路径覆盖
对于不可重点最小路径覆盖,拆点后跑二分图最大匹配

最小路径覆盖=原图的结点数-新图的最大匹配数

这里有好多坑 qwq 证明会后补(大概

 


一个非常弱的准退役OIER