I want to know if there is a way to implement KM method, so that the vertex cover value in the algorithm won't be negative.
Or maybe my implementation won't have negative vertex value.
If someone can help me with that, I would be very thankful.
This is my KM algorithm's code: http://codepad.org/O0W8ZnHx
(I think it is the same with the standard implementation, except for the slack array)
I want to know this is because of one of the problem in Saratov State Judge:
http://acm.sgu.ru/problem.php?contest=0&problem=206
I have gotten AC for this problem.
But the vertex value must be positive(or zero) in this problem, so I am wondering if the code itself is correct or is the test case too weak.
After a long time of thinking,
I think the algorithm itself won't have negative vertex weight.
I've proved it and the proof is quite simple actually.