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

Автор alurquiza, история, 9 лет назад, По-английски

How can I solve the problem Hooligan?, problem H of the ACM-ICPC Latin American Contest 2009. Could anyone help me? http://coj.uci.cu/24h/problem.xhtml?pid=1210

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

First, we suppose greedily that our dream team wins all of its missing matches. After this, it should have P points. Then, build a graph with nodes x1, x2, ..., xn - 1. Now, between xi and xj (i ≠ j), put an edge in each direction with capacity equal to the number of games missing between teams i and j. Use a node B, which has an edge towards every xi with capacity equal to the number of matches the ith team still has to play, and a node E, in such a way that there is an edge from each xi to this node with capacity equal to P - pi, where pi are the points that the ith team already has. Your dream team can be a champion iff the maxflow from B to E equals the number of missing matches.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

This is a famous Max Flow problem, more info here