恕我直言,这题几乎所有的题解都不知所云,有的题解甚至认为仅仅是“一道二分图最大匹配”,或者将重点放在匈牙利或者dinic这些基本算法上,一塌糊涂。
这题是最长反链的一个模板,并且有不止一种转化方法(如果 _jimmywang_ 的题解无误)。运用 Dilworth 定理转化为传递闭包上的最小路径覆盖只是其一,并且最小路径覆盖已有板子题。故所有认定此题为最小路径覆盖而不加以解释,或者将重点放在如何求最小路径覆盖上的题解,都是不合格的题解。
如果要用最小路径覆盖的做法,则本题的重点应当是如何由 Dilworth 定理转化到最小路径覆盖上,以及为什么要做传递闭包。多数题解对此毫无解释或者解释得乱七八糟,这是很不应该的。
目前,@Stairs_upon_temple 的题解,@yuruilin2026 的题解,@wuzijie 的题解,@Weekoder 的题解,@crz_qwq 的题解,@Stone_Xz 的题解,@Stars_visitor_tyw 的题解 全都不合格,建议修改。有且仅有 @_jimmywang_ 的题解质量较高。@JustPureH2O 的题解看上去还可以,但我有些地方没看懂,不做评价。