【BZOJ1143】【CTSC2008】祭祀

一眼秒是二分图最大独立集

然而建图居然建错了= =

这里要求的其实叫做最长反链长度

有个定理:最长反链长度=最小链覆盖

最小链覆盖即可以交叉的最小路径覆盖

不可交叉的直接连边即可;然而可交叉的怎么做?

每个点拆成两个点 若\(i\)能到\(j\)从左边的\(i\)向右边的\(j\)连边

这样就可以跳过一些之前已经选出的点,达到可交叉的目的。

听说原题更神 这题被删了后面两问= =

说点什么

  Subscribe  
提醒