Problem #3 (About maximum flow and minimum cuts) (25 points) A company has 4 branches in one city and plans to move some of them to another city. The ith branch costs ai per year if it stays in the original city and b; per year if it is moved to the new city. The company also needs to pay an extra Gij per year for traveling between branches i and j if they are not in the same city. The company must decide which branches should be moved to the new city in order to minimize the total yearly cost. The costs 4i, b; and Gij are given in the following table. 2 3 4 b; 80 130 110 ; 1 120 10 15 2 90 5 15 15 3 150 10 5 20 4 170 25 20 10 210 20 1. Formulate this problem as a maximum flow problem (Ilint: In this problem, you will care more about the minimum cul than the marimum flow). In particular, you should draw the vertices and arcs of the network. You should also clearly indicate the capacity of cach arc, together with the source and the sink of the maximum flow problem. 2. Use Ford-Fulkerson's algorithm to solve this maximum flow problem starting from the zero-llow. Draw a new residual network after cach iteration you perform Problem #3 (About maximum flow and minimum cuts) (25 points) A company has 4 branches in one city and plans to move some of them to another city. The ith branch costs ai per year if it stays in the original city and b; per year if it is moved to the new city. The company also needs to pay an extra Gij per year for traveling between branches i and j if they are not in the same city. The company must decide which branches should be moved to the new city in order to minimize the total yearly cost. The costs 4i, b; and Gij are given in the following table. 2 3 4 b; 80 130 110 ; 1 120 10 15 2 90 5 15 15 3 150 10 5 20 4 170 25 20 10 210 20 1. Formulate this problem as a maximum flow problem (Ilint: In this problem, you will care more about the minimum cul than the marimum flow). In particular, you should draw the vertices and arcs of the network. You should also clearly indicate the capacity of cach arc, together with the source and the sink of the maximum flow problem. 2. Use Ford-Fulkerson's algorithm to solve this maximum flow problem starting from the zero-llow. Draw a new residual network after cach iteration you perform