How to solve this problem ? Flow seems not enough because of the vertexes of "anything" type.

Flow can solve it but there's a better way in fact.

Edited by author 11.10.2009 21:40

Could you tell me, please, how to construct the graph for a flow ?

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

I tried to use Kuhn (max pair-combination), but get WA#11. And don't know, what to do next...

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.

My algo is O(n^3),but it got TLE 11!
What is right algo here?

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.

But why will the maximum match in this graph will be answer to the problem?

I used a Hopcroft-Karp algorithm to solve this problem and got AC in 31 ms. So, not bad :)