1. Dinic.cpp

Problem Description:

Implement any s-t-max-flow algorithm.

INPUT FORMAT: The first line contains k, the number of problems. Then descriptions of the problems follow. The first line contains n (the number of vertices) and m (the number of edges). The second line contains s, t ∈ {1, . . . , n} (the source and the sink). Then m lines follow. Each line contains three integers u, v, c, where u, v ∈ {1, . . . , n} and 1 ≤ c ≤ 1, 000, 000; this means that there is edge (u, v) with capacity c in the graph. We have 2 ≤ n ≤ 1, 000 and 1 ≤ m ≤ 10, 000.

OUTPUT FORMAT: The output contains one line for each problem—the value of the maximum s-t flow

2. Problem2.cpp

Problem Described in prob2.png