algorithm - 有向无环图中的最小路径覆盖

Question

我在这里要问的问题在stack overflow之前已经被问过了。 但是我无法正确理解 Skiminok 发布的解决方案。

这是 Link .

我用给定的两个示例测试用例尝试了上面链接上发布的解决方案，但我无法得到正确的答案。

对于测试用例 1::

N=3 和 K=2

5 4 7

DAG 将是:

注意:我构建了上面的 DAG 考虑到:

设 pi 和 pj 是两个不同的问题。然后当且仅当 pj 可以在 pi 之后直接在同一天连续求解时，我们将绘制一条从 pi 到 pj 的有向边。即，必须满足以下条件:

i < j，因为你应该早点解决难度较小的问题。

|vi - vj| >= K(评级要求)。

然后我构建了二分图考虑::

对于原始 DAG 的每个有向边 (u, v)，应该向二分图中添加一个无向边 (au, bv)，其中 {ai} 和 {bi} 是大小为 n 的两个部分。

答案=上面二分图中的最大基数匹配。

上面二部图中的最大基数匹配=1(绿色边)

但答案是2。

类似示例测试用例 2:

5 1

5 3 4 5 6

上图中的 MAX 基数大于一个，但正确答案是 1。

我想我没有正确实现它，请你告诉我哪里出错了或者还有其他方法吗

谢谢!

Answer 1

我自己找到了答案， 第二天我发布了这个问题。

我的解决方案通过了所有测试用例。

我在最后一步出错了。 实际上，答案/解决方案是 SET B 中不包含最大二分匹配边的顶点总数。

例如示例测试用例 1::

最大匹配 M={(1A,3B)}。

没有最大匹配的边入射到两个顶点(顶点1和顶点2)。所以答案等于这样的顶点数=2

对于测试用例 2::

最大匹配 M={(1A,2B),(2A,3B),(3A,4B),(4A,5B)}。

没有最大匹配的边入射到一个顶点(顶点1)。所以answer等于1