问题描述
我要问这方面的问题已经在之前堆栈溢出问。但我没能正确理解由发布解决方案的 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
这篇关于在向无环图最小路径覆盖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！