When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Pi-nan's blog

By Pi-nan, history, 4 years ago, In English

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

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