Editorial for ICPC NWERC 2011 F - Pool Construction
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Solution: maximum flow
- First, fill all boundary squares
- Construct the following flow graph:
- Vertices: source, sink, every square
- Edge from source to boundary square with capacity
- Edge from source to non-boundary grass square with capacity
(dig)
- Edge from non-boundary hole square to sink with capacity
(fill)
- Edges between connected squares with capacity
(boundary)
- You can show that the cost of a cut of this graph equals the cost of splitting it into grass and holes along this cut
- So find the minimum cut, i.e., the maximum flow
Comments