11383 - Golden Tiger Claw

[baodog]

I believe this problem is the Primal-Dual of a networkflow problem.
However, I can't quite get it into the right form. Does it require full
integer programming?

[mf]

It can be shown that the maximum weight of a perfect matching in bipartite graph with weights w_ij is equal to the minimum value of the sum of row and column labels.
Kuhn-Munkres algorithm is the constructive proof.

[sonyckson]

Hi!... how do you get the rows and cols values after getting the maximum weight???( greedy? ), Thanks, Eric.

[mf]

You get them as a by-product of Kuhn-Munkres algorithm.

[shanto86]

yes, as mf said it is nothing but plain implementation of Kuhn-Munkres. But i thought it will be solved least. Unfortunately and very surprisingly it was the first problem which got accepted in the contest.

[baodog]

Nevermind, got accepted...
No extra spaces or blanks in the output.
Numbers are separated by one space.

[yasuh]

Hello.
I cannot understand how to change to matching problem
Would someone show me an example?

[shanto86]

I cant understand one thing, my pc is slow there is no doubt about that, it took approximately 8s, but in judge pc it got AC in only 0.76s. but when i asked official to check my code against judge pc it was more than 3s. But on the same data it is only 0.76s now! how did it happen? anybody any idea?

[Observer]

I'm greatly pulling down the acceptance rate... :- )

Could anyone offer some test cases? I am getting WA...

[EDIT] Never mind. I've found a stupid flaw in my alternate-path finding routine. Now I'm facing TLE.

[EDIT] Accepted. Now with the slowest time in ranklist~

[ardiankp]

Hi,

Can anyone explain what does J_{Gl}(S) mean in the paper linked?

Thanks

[mf]

J_G(S) means the set of vertices adjacent to S, i.e the set of all y such that (x, y) is an edge of G, and x is in S.