---

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int V = 6, s = 0, t = 5, INF = 1e9;
int capacity[V][V] = {
    {0,10,5,0,0,0}, {0,0,0,10,0,0}, {0,0,0,5,10,0},
    {0,0,0,0,0,10}, {0,0,0,5,0,10}, {0,0,0,0,0,0}
};

int flow[V][V], residual[V][V], parent[V];
bool visited[V];

bool FindPath(int u) {
    if (u == t) return true;
    for (int v = 0; v < V; v++) {
        if (!visited[v] && residual[u][v] > 0) {
            visited[v] = true;
            parent[v] = u;
            if (FindPath(v)) return true;
        }
    }
    return false;
}

int FordFulkerson() {
    for (int u = 0; u < V; u++)
        for (int v = 0; v < V; v++) {
            flow[u][v] = 0;
            residual[u][v] = capacity[u][v];
        }

    int max_flow = 0;
    while (true) {
        fill(parent, parent + V, -1);
        fill(visited, visited + V, false);
        parent[s] = s;
        visited[s] = true;

        if (!FindPath(s)) break;

        int bottleneck = INF;
        for (int v = t; v != s; v = parent[v])
            bottleneck = min(bottleneck, residual[parent[v]][v]);

        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            flow[u][v] += bottleneck;
            flow[v][u] -= bottleneck;
            residual[u][v] = capacity[u][v] - flow[u][v];
            residual[v][u] = capacity[v][u] - flow[v][u];
        }
        max_flow += bottleneck;
    }
    return max_flow;
}

int main() {
    auto start = high_resolution_clock::now();

    cout << "Max flow: " << FordFulkerson() << "\n";

    double ms = duration<double, milli>(high_resolution_clock::now() - start).count();
    cout << "Time: " << ms << " ms\n";

    return 0;
}