You are given a flow network G with n vertices, including a source s and sink t, and m directed edges with integer capac

[answerhappygod]

You are given a flow network G with n vertices, including asource s and sink t, and m directed edges with integercapacities.
Your friend will ask you several queries of the form: “If anedge were to be added to G, going from vertex a to vertex b withcapacity c, what would the maximum flow of the modified networkbe?” Note that each query considers adding an edge to the originalflow network, so the modified network has m + 1 edges.
Before asking any queries, your friend gives you some time toprepare, which you can spend on precomputation.
Using maximum flow algorithms such as Ford- Fulkerson andEdmonds-Karp). Design an algorithm which performs any requiredprecomputation and then answers each query in constant time,subject to the following restrictions:
1) O(nm 2 ) precomputation; b = t and c = 1 inall queries.