Please read the new rule regarding the restriction on the use of AI tools. ×

iceman91's blog

By iceman91, 12 years ago, In English

I am trying to solve this problem. In this problem we have to reassign the scores such that they are possible and the absolute difference between original scores and the new scores is minimized. Now for assigning possible scores, I can construct a bipartite graph (X,Y) where nodes in X correspond to all the matches that are going to take place and nodes in Y correspond to all the team that are participating. There is an egde (x,y) iff y is one of the teams participating in match x. Finding maximum flow in this network gives me an optimal assignment. But how do I deal with the constraint of minimizing the absolute difference in this kind of network? If I am wrong with my approach, please do correct me.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You almost solved the problem. Add edges from Y vertices to sink with capacity a[Y] (points of wizard Y). Once you find max-flow, answer will be sum of two values: (points of wizard Y — flow to vertex Y) over all Y and not used matches (vertex X).

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you please explain adding vertices to sink in more detail. Thanks :) !