#11506 - Angry Programmer

Solved By:	wesley
Theory Difficulty:	medium
Coding Difficulty:	easy
Algorithms Used:	max flow
Solution Description:	We're trying to find the minimum cut in the graph, so we can conversely determine maximum flow. We also have vertex capacities because we can blow up computers. So, split each node (except 1 and M) into two nodes, in and out. If you have an edge like (2, 3), connect 2out to 3in and 3out to 2in, both with the same capacity. If you have an edge like (1, 4), connect 1 to 4in and 4out to 1. For each computer cost, draw and edge from Cin to Cout with that cost. Connect the source to vertex 1 and connect vertex M to the sink, and run max flow to get your answer.