Max-flow and linear programming are two big hammers in algorithm design: each are expressive enough to represent many poly-time solvable problems. Some problems are obvious applications of max-flow: like finding a maximum matching in a graph. What I'm looking for are examples of problems that can be solved via clever encodings as flow problems or LP problems — ones that aren't obvious. I'm looking for questions at a level suitable for a homework problem for an advanced undergraduate or beginning graduate course in algorithms.
Any ideas?
Best Answer
Determining whether a sports team has been mathematically eliminated from qualifying for the playoffs is a cute application of max-flow min-cut:
http://www.cs.princeton.edu/courses/archive/spr03/cs226/assignments/baseball.html