Edmonds Karp - Max Flow algorithm - runs in O(V^3 * E) using adjacency matrix
#define INF 0x3f3f3f3f
// mf: max flow (our solution, eventually)
// f : min f at the time
// s : source
// t : sink
int mf, f, s, t;
// parent, for BFS
vi p;
// max # of vertices we could have
#define MV 1000
int res[MV][MV];
void augment(int v, int lo) {
if (v == s) {
// base case: we reach source, and resolve 'f' to the minimum edge
f = lo;
return;
} else if (p[v] != -1) {
// wonder... is this check redundant? ==> no. It is needed because not
// necessarily have v -> u (back) for all u -> v
// recursive call
augment(p[v], min(lo, res[p[v]][v]));
// NOTE: changing with 'f', not 'lo'... why?
// because we're doing recursive calls, updating 'f' once we arrive at
// 's', at which point the global 'f' is updated, 'augment' returns up the
// stack, and these values need to be updated with that 'f', not just what
// 'lo' was at the time
//
// update forward res edges u -> v (i.e. p[v] -> v) with -f
// update backwrd res edges v -> u (i.e. v -> p[v]) with +f
res[p[v]][v] -= f;
res[v][p[v]] += f;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// for each case, setup res, s, t
cin >> s >> t;
// init to 0, need to do this cause using adj matrix
REP(i, MV)
REP(j, MV) res[i][j] = 0;
// of the form:
// node_u node_v uv_capacity
int u, v, c;
while (cin >> u >> v >> c) {
cin >> u >> v >> c;
res[u][v] = c;
}
// max flow, initially 0
mf = 0;
for (;;) {
// don't forget this. 'f' needs to be reset each time
// or does it?... don't see why
// ==> YES: it is needed,
// ==> See below: <f needs to be 0>
f = 0;
// here, dist is the 'hop-count' from s to t
// but the actual 'weights' (i.e. capacities) of the edges are
// handled in 'res', initially equal to original values, but
// change over the course of the algorithm
vi dist(MV, INF);
dist[s] = 0;
// don't forget this part
p.assign(MV, -1);
queue<int> q;
q.push(s);
while (!q.empty()) {
auto u = q.front();
q.pop();
if (u == t) break; // Exit condition: reach the sink
REP(v, MV) {
// Interpretation
// 1: res[u][v] > 0
// ==> v reachable from u
// 2: dist[v] == INF
// ==> unvisited
if (res[u][v] > 0 && dist[v] == INF)
dist[v] = dist[u] + 1, q.push(u), p[v] = u;
}
}
// BFS path has been created and stored by 'p', now augment.
// When this completes, we will know the minimum flow 'f' in this path ***IF
// ANY*** why IF ANY? ==> because when 'f' == 0, we cannot send any more
// flow, so we are DONE
// ==> See above: <f needs to be 0>
augment(t, INF);
if (f == 0) break;
// we increase 'mf' maxflow solution for this case, by 'f' -> the flow that
// we still have the capacity to send.
mf += f;
}
// print 'mf' the maximum flow.
cout << mf << endl;
return 0;
}