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

Question

我将要问的问题已经在Stack Overflow上被问过了。但是我无法正确理解Skiminok发布的解决方案。

以下是链接：Link . 我尝试使用上面链接中提供的两个测试用例的解决方案，但我无法获得正确答案。

对于测试用例1：

N=3和K=2

5 4 7

DAG如下所示： 注意：我构建了上述DAG，考虑到：

假设pi和pj是两个不同的问题。如果pj可以在同一天连续地直接在pi之后解决，则我们将从pi向pj绘制一个有向边。即必须满足以下条件：

i=K（评级要求）。

然后我构建了二分图，考虑到：

对于原始DAG的每条有向边（u，v），应向二分图添加一条无向边（au，bv），其中{ai}和{bi}是大小为n的两个部分。 答案=上述二分图中的最大基数匹配。

上述二分图中的最大基数匹配=1（绿色边缘）

但是答案是2。

类似的样本测试用例2：

5 1

5 3 4 5 6

上述图中的MAx基数大于1，但正确答案为1。

我认为我没有正确实现它，请告诉我我的错误在哪里或是否有其他方法。

谢谢！

- Ritesh Kumar Gupta

Answer 1

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

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

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

例如，在样本测试用例1中：

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

最大匹配的没有一条边与两个顶点（顶点1和顶点2）相交。因此，答案等于这样的顶点数量=2

对于测试用例2：

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

最大匹配的没有一条边与一个顶点（顶点1）相交。因此，答案等于1。

- Ritesh Kumar Gupta