#BZOJ1143

BZOJ1143 [CTSC2008]祭祀river 二分图匹配 最小链覆盖

  给出一个有向图。求最小链覆盖。   首先说两个概念:    链:一条链是一些点的集合,链上任意两个点x,y,满足要么x能到达y,要么y能到达x。    反链:一条反链是一些点的集合,链上任意两个点x,y,满足x不能到达y,且y也不能到达x。  这题就是求最长反链长度。  有两个定理:  最长反链长度=最小...