Блог пользователя Pi-nan

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

can anyone explain to me how to solve this problem Ceil and Duel using min-cost max flow?

my approach was to build a flow network i.e. if node i have atk value >= node j ceil value then there will be an edge from j to i with capacity 1 and cost (atk[i]-ceil[j]), similarly if node i has def value > node j ceil value then there will be edge from j to i with capacity 1 and cost 0, and then connect all ceil's node to super source i.e. superSource -> ceil, and connect all atk and def node to super sink i.e. atk/def -> superSink with capacity 1 and cost 0. after building this network we will find min_cost_max_flow and after this, if all atk/def nodes are visited then we will add ceil[i] such that ceil's ith node is not used. I don't know why this is failing on test 28.

Link to my submission

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