#10594 - Data Flow

Solved By:	wesley
Theory Difficulty:	hard
Coding Difficulty:	medium
Algorithms Used:	dijkstra max flow other graph
Solution Description:	This is a minimum-cost maximum flow problem. Basically, it's the combination of shortest path and maximum flow. The general idea is not too difficult. You do Edmonds-Karp to get the maximum flow, but you replace the BFS with a weighted shortest path algorithm. Dijkstra is the best choice, except that the graph will have negative costs after you reverse edges. You can do Bellman-Ford, but unfortunately that's too slow for this problem (unless you're lucky in C perhaps). Luckily, there exists a compromise. You can run Bellman-Ford once at the beginning of the algorithm to set the graph up in such a way that Dijkstra will work from that point on. In this problem, because there are no negative costs to begin with, you don't need Bellman-Ford at all, and you can use Dijkstra to initialize the graph, but it doesn't matter much runtime-wise. I suggest reading the following to understand how this "graph initialization" part works. Read the subsection "Successive Shortest Path Algorithm": http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2