Answer Happy

Question 4 You are given a flow network G with n vertices, including a source s and sink t, and m directed edges with integer capacities. Your friend will ask you several queries of the form: "If an edge were to be added to G, going from vertex a to vertex b with capacity c, what would the maximum flow of the modified network be?" Note that each query considers adding an edge to the original flow network, so the modified network has m+1 edges. Before asking any queries, your friend gives you some time to prepare, which you can spend on precomputation. Design an algorithm which performs any required precomputation and then answers each query in constant time, subject to the following restrictions: 4.2 [6 marks ]O(nm2) precomputation; c=1 in all queries.