Take the code you wrote for the Ford-Fulkerson algorithm for the maximum flow on a directed graph with capacities, and implement scaling on top of this code. You write a function

void maximum flow scale(int n, int s, int t, int *capacity, int *flow)

with the same arguments as the function maximum flow in Homework 3:

- n: the number of vertices of the graph,

- s: the start vertex,

- t: the target vertex

- capacity: the matrix of edge capacities.

- flow: the matrix used to return the maximum flow.

Scaling is a method to speed up the Ford-Fulkerson Algorithm for flows with large integer capacities. You construct a sequence of auxiliary capacities CAPi

from the original

capacities CAP0 by halving all capacities (integer division: rounding downward). Let CAPk be the last of these matrices which is not all zero. You solve first the problem with capacities

CAPk with your Ford-Fulkerson code; then you take the flow you found, double all flow values,and take that as initial flow for the capacities CAPk−1, and solve the problem for those capacities. You continue this doubling until you are back at the original 

capacities. Since each step has a cut of size at most n − 1, each of the intermediate flow problems can augment at most n − 1 times, and there are only log(MaximumCapacity) many intermediate problems.