Lesson 5

In Python, you can find the maximum flow and minimum cut like this.

import networkx as nx
G = nx.DiGraph()

for u, v, c in [
    ('S', 'A', 6), ('S', 'B', 1), ('S', 'C', 10),
    ('A', 'B', 2), ('C', 'B', 2), ('A', 'E', 1),
    ('A', 'D', 4), ('D', 'E', 2), ('D', 'G', 5),
    ('E', 'G', 10), ('B', 'E', 20), ('C', 'F', 5),
    ('E', 'F', 6), ('F', 'T', 4), ('G', 'T', 12)
]:
    G.add_edge(u, v, capacity=c)

print(nx.maximum_flow(G, 'S', 'T')[0])
print(nx.minimum_cut(G, 'S', 'T'))

13
(13, ({'C', 'F', 'S'}, {'T', 'E', 'B', 'G', 'D', 'A'}))