Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Pi-nan's blog

By Pi-nan, history, 6 weeks 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