Help with algo please
How to solve this problem ? Flow seems not enough because of the vertexes of "anything" type.
Re: Help with algo please
Flow can solve it but there's a better way in fact.
Edited by author 11.10.2009 21:40
Re: Help with algo please
Could you tell me, please, how to construct the graph for a flow ?
Re: Help with algo please
you should construct bipartite graph.
for example , you have people with ranks:
2 4 6 8 10
2 , 6 , 10 - to the left side
4 , 8 - to the right side
Re: Help with algo please
I tried to use Kuhn (max pair-combination), but get WA#11. And don't know, what to do next...
Re: Help with algo please
You always can put all the people with skill < 2 (modulo 4) to the left part and all the people with skill >= 2 (modulo 4) to the right. Definitely, all the edges will connect vertices from different parts, so this graph will be bipartite.
Re: Help with algo please
My algo is O(n^3),but it got TLE 11!
What is right algo here?
Re: Help with algo please
My algo is O(n^2*m) and AC in 0.093
It is standart bipartite matching algo
Re: Help with algo please
My algo is O(n^2*m) and AC in 0.093
It is standart bipartite matching algo
I was use Hopcroft_Karp algo (from wiki) and AC. 0.031 s.
Re: Help with algo please
You always can put all the people with skill < 2 (modulo 4) to the left part and all the people with skill >= 2 (modulo 4) to the right. Definitely, all the edges will connect vertices from different parts, so this graph will be bipartite.
But why will the maximum match in this graph will be answer to the problem?
Re: Help with algo please
I used a Hopcroft-Karp algorithm to solve this problem and got AC in 31 ms. So, not bad :)