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

Question

我在这里要问的问题是在堆栈溢出之前已经被问过了.但我无法正确理解Skiminok发布的解决方案.

这是链接.

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

对于测试用例1 ::

N = 3且K = 2

5 4 7

DAG将::

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

让pi和pj成为两个不同的问题.然后我们将绘制从pi到pj的有向边,当且仅当pj可以在pi之后直接在同一天连续解决.即,必须满足以下条件:

我<j,因为你应该先解决较不困难的问题.

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

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

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

答案=上述二分图中的最大基数匹配.

上述二分图中的最大基数匹配= 1(绿色egde)

但答案是2.

类似的样本测试案例2:

5 1

5 3 4 5 6

上图中的MAx基数超过一个,但正确的答案是1.

我想我没有正确实现它,请你能告诉我在哪里犯错误或者是否还有其他方法

谢谢!

Answer 1

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

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

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

例如示例测试用例 1::

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

没有最大匹配的边入射到两个顶点（顶点 1 和顶点 2）。因此答案等于此类顶点的数量=2

对于测试用例 2::

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

最大匹配的边没有入射到一个顶点（顶点 1）。因此答案等于 1