Dear all,

I am having trouble understanding the solution to this problem on Kattis. I hope someone can help me explain the solution.

Summary of the problem: Given a 2D binary table, each ceil is either high or low. The cost go from a low ceil to a high one is A, the cost to "low down a high ceil" is B. We must find the minimum total cost of traveling through all columns and then all rows by lowing down some ceils?

Summary of the solution: Create a graph with n * m (ceils in the table) + 2 (source and sink) vertexes, connect the source to all low ceils and connect all high ceils to the sink with edges having capacity of B, connect ceils to their neighbors (regardless of the heights) with edges having capacity of A. The answer is the min cut max flow from source to sink.

I try my best but still unable to understand the meaning of this solution. I think this is a great application problem of max flow min cut, so I hope someone can help me.

Thank you so much for your time and consideration.