Menu
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.
Here is the Link .
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.
For the test case 1::
N=3 and K=2
5 4 7
The DAG will be::
Note :I have constructed the above DAG Considering:
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 < j, because you should solve the less difficult problem earlier.
|vi - vj| >= K (the rating requirement).
Then I constructed the Bipartite graph considering::
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 .
maximum cardinality matching in above bipartite graph =1 (Green colored egde)
But the answer is 2.
Similarly Sample Test Case 2:
5 1
5 3 4 5 6
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
Thanks!
835
A minimum path cover (MPC) of G is a path cover of G of minimum cardinality. If each edge e of G has a non-negative weight w(e), then a minimum weight minimum path cover is a minimum path cover MathML which minimizes the sum of the weights of the edges of the paths of MathML, that is, MathML Σ e∈P w(e).
The maximum number of edges in a DAG with n vertices is Θ(n2).
So (since s and t must always be included) there are at most 2n−2 paths. This bound is tight, for a complete DAG (one in which every pair of vertices is connected by an edge, oriented consistently with a single topological order).
Given a Weighted Directed Acyclic Graph and a source vertex in the graph, find the shortest paths from given source to all other vertices. For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm.
I found the answer myself , the next day i posted this question.
And my-solution passed all test cases .
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.
For Example on sample test case 1::
Maximal Matching M={(1A,3B)}.
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
For test case 2::
Maximal Matching M={(1A,2B),(2A,3B),(3A,4B),(4A,5B)}.
No edge of maximal matching is incident upon one vertex (Vertex 1).So answer is equal to 1
153
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
