For this assignment you are going to do some code using the graph algorithms that have been discussed in class. As with all the assignments, you can write this in whatever language you want, but I have to be able to compile and run it under Linux on the lab machines. What you turn in will be graded for correctness and speed. It might also be used in a future assignment so keep that in mind and try to build flexible and robust data structures. You will use this data structure to solve the following problem. You might also use some other data structures to go along with it, but you don't have to write those if you can find a good library for them.
For this assignment you will be doing a maximum flow problem on a large graph. The vertices in the graph will represent cities and the edges will represent routes between the cities that a company has for transporting things. Each edge has a capacity telling you how many tons of material can be transported each day on that route. Your task is to determine whether that network can fill certain needs. The needs will be given to you as a certain amount of material being produced at various cities that need to be sent to other cities.
The interface for this program will be all text. You will read from standard input and write to standard output. The input will begin with a specification for the graph followed by the test cases. Each test case will list a set of source cities and how much material each produces and a list of sink cities and how much each of those cities will want. You have to tell if the network can fulfill those demands. All the material in question is identical. Basically, your company makes one product that you have to get from factories out to retail.
The input begins with a line with two numbers, V and E, the number of cities and the number of routes. That is followed by V lines with city names and E lines with the format "city1 city2 capacity". We will stick with integer capacities for simplicity.
Following that will be a number telling you how many test cases there are. Each test case will have two lines. The first line is the source cities and how much they produce given as "name1 amount1 name2 amount2 ...". The second line has the same format, but it is sink cities and how much they want. The total amount of the sources and sinks will always be the same.
For each test case, you will solve the max flow and tell whether the network was able to get all the source material to the sinks. If the answer is yes, you print "The network is sufficient." If the answer is no, you should print a list of shortcomings. That list will have city names and how much they were off by as a comma separated list. That list should be sorted by how much the city was off with ties broken by alphabetical order of city names. Sources that can get their material out should have a positive value while sinks that can't get material in should have a negative value.
Plus, here is a small input that is good for debugging. debug in : debug out