Hello All,
I am trying to solve maximum flow, and I am experiencing some problems formatting the output.
Here is some pseudocode I am trying to implement.
c [u, v] is capacity from u to v, f [u, v] is the flow, cf [u, v] is the residual capacity.
for each edge (u, v) in the graph do:
f [u, v]: = 0; f [v, u]: = 0
cf [u, v]: = c [u, v], cf [v, u]: = c [v, u]
While there is a path p from s to t in residual flow graph do
r: = min (cf [u, v]: (u, v) is included in p)
for each edge (u, v) in p do
f [u, v]: = f [u, v] + r, f [v, u]: = - f [u, v]
cf [u, v]: = c [u, v] - f [u, v], cf [v, u]: = c [v, u] - f [v, u]
Input
The first row contains an integer that specifies the number of vertices in V.
The second line consists of two integers s and t that defines the corners of source and outlet.
The third line consists of a number indicating | E |, ie the number of edges in the graph.
The following | E | rows consisting each of three integers corresponding to an edge.
The corners are numbered from 1 upwards. If you entered a corner of V we let V = {1, 2 ,..., a}. An edge is indicated by the endpoints (only from the corner and then to-corner) followed by its capacity.
For example, a graph, for example, is coded as follows.
4
1:04 a.m.
5
1 2 1
1 2 3
2 4 2
3 2 2
3 4 1
Output
The first row contains an integer that specifies the number of vertices in V.
The second line consists of three integers s, t, and the flow from s to t.
The third row contains an integer that specifies the number of edges with positive flow.
Then assigned a number for each such edge. The edge is described by three numbers in a similar way as the input, but instead of capacity, we now have flow.
Example: If we have the graph above as input, so output can look like this.
4
1 4 3
5
1 2 1
1 2 3
2 4 2
3 2 1
3 4 1
I am having problems formatting input. Can someone help?
