在向无环图最小路径覆盖 [英] Minimum path cover in directed acyclic graph

问题描述

我要问这方面的问题已经在之前堆栈溢出问。 但我没能正确理解由发布解决方案的 Skiminok

The question I am going to ask here has already been asked before in stack overflow. But I am not able to understand properly the solutions posted by Skiminok.

下面是链接。

我试着贴在给定的两样本测试案例上面的链接的解决方案，但我不能得到正确的答案。

I tried the solution posted on the above link with the given two sample test-cases ,but i am not able to get the correct answer.

有关测试案例1 ::

For the test case 1::

N = 3和K = 2

N=3 and K=2

5 4 7

该DAG将是::

注：我已经建造了上述DAG考虑：

Note :I have constructed the above DAG Considering:

让PI和PJ是两个不同的问题。然后，我们将以此为定向边从圆周率pj则当且仅当PJ可以圆周率在同一天后直接得到解决，连续。即，在下列条件必须满足：

Let pi and pj be two different problems. Then we will draw a directed edge from pi to pj if and only if pj can be solved directly after pi on the same day, consecutively. Namely, the following conditions have to be satisfied:

I＆LT; Ĵ，因为你要解决的难度较低的问题前面。

i < j, because you should solve the less difficult problem earlier.

|六 - VJ | > = K（评级要求）。

|vi - vj| >= K (the rating requirement).

然后我构建的二分图考虑到::

Then I constructed the Bipartite graph considering::

对于每一个有向边（U，V）的原始DAG应该加上一个无向边缘（AU，BV）的二分图，其中{爱}和{双}是一个大小为两部分。

For each directed edge (u, v) of the original DAG one should add an undirected edge (au, bv) to the bipartite graph, where {ai} and {bi} are two parts of size n.

答案=最大基数二部图上面的匹配

The answer =maximum cardinality matching in above bipartite graph .

最大基数二部图上面的匹配= 1（绿色的EGDE）

maximum cardinality matching in above bipartite graph =1 (Green colored egde)

但答案是2。

同样样品测试案例2：

5 1

5 3 4 5 6

5 3 4 5 6

最大基数在上图是一多，但正确答案是1。

The MAx cardinality in above graph is MORE THAN ONE ,but the Correct answer is 1.

我觉得我没有正确地实现它，请你能告诉我在哪里犯错误或者有没有其他的方法

I think i am not implementing it correctly,please can you tell where i am making mistake Or is there any other Method

谢谢！

推荐答案

我发现自己的答案， 第二天，我张贴了这个问题。

I found the answer myself , the next day i posted this question.

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

And my-solution passed all test cases .

我是会犯错的最后一步。 其实答案/解决方案是顶点集合B中不包含的最大偶匹配边的总数。

I was making mistake in the last step. Actually the Answer/solution is the total Number of vertices in SET B that does not contain the edge of Maximal Bipartite Matching.

例如样品测试案例1 ::

For Example on sample test case 1::

极大匹配M = {（1A，3B）}。

Maximal Matching M={(1A,3B)}.

最大匹配的无边缘入射到两个顶点（顶点1和顶点2）。所以答案是等于这样的顶点数量= 2

No edge of maximal matching is incident upon two vertices (Vertex 1 and Vertex 2).So answer is equal to number of such vertex=2

有关测试用例2 ::

For test case 2::

极大匹配，M = {（1A，2B），（2A，3B），（3A，4B），（4A，5B）}

Maximal Matching M={(1A,2B),(2A,3B),(3A,4B),(4A,5B)}.

最大匹配的无边沿是在一个顶点（顶点1）。所以答案等于1事件

No edge of maximal matching is incident upon one vertex (Vertex 1).So answer is equal to 1

这篇关于在向无环图最小路径覆盖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！