Блог пользователя iceman91

Автор iceman91, 12 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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