#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>

using namespace std;

class Graph{

    //DATE MEMBRE
private:

    int m_graph_nodes;
    //numar de noduri

    vector<vector<int>> m_graph_adjacency_list;
    //lista de adiacenta

    vector<vector<pair<int,int>>> m_graph_adjacency_list_with_costs;
    //lista de adiacenta pentru graf cu costuri

    vector<vector<int>> m_costs_matrix;
    //matricea de costuri pentru grafuri ponderate

    vector<vector<int>> m_capacities;


public:
    //METODELE CLASEI

    //CITIRILE

    void read_graph_with_costs_as_costs_matrix(char *file);
    //citire graf orientat ponderat cu matricea costurilor

    void read_transport_routes(char *file);
    //citire retea de trasnport

    //ALGORITMI FUNDAMENTALI

    vector<vector<int>> roy_floyd();
    //algoritmul roy floyd -> returneaza matricea drumurilor din matricea costurilor asociata grafului apelant

    int edmonds_karp();
    //algoritmul edmonds karp -> returneaza fluxul maxim

    //HELPERE
    void print_path_matrix(vector<vector<int>> path_matrix, char *file);
    //functia care afiseaza in fisier matricea drumurilor

//METODE UTILE IN METODELE PUBLICE
private:
    int minimum_length_BFS(vector<vector<int>>& flows, vector<int>& tata, vector<int>& viz);
    //pentru edmonds karp
};

//METODELE PUBLICE

//  CITIRI

void Graph::read_graph_with_costs_as_costs_matrix(char *file) {
    ifstream f(file);
    vector<int> aux;

    f >> this->m_graph_nodes;

    m_costs_matrix.push_back(aux);

    for(int i = 1; i <= this->m_graph_nodes; i++){
        vector<int> linie;
        linie.push_back(0);

        for(int j = 1; j <= this->m_graph_nodes; j++){
            int val;
            f >> val;
            linie.push_back(val);
        }

        m_costs_matrix.push_back(linie);
    }
}

void Graph::read_transport_routes(char *file) {
    ifstream f(file);
    int number_edges;
    vector<int> aux;

    f >> this->m_graph_nodes;
    this->m_graph_adjacency_list.assign(this->m_graph_nodes + 1, aux);

    aux.assign(this->m_graph_nodes + 1, 0);
    this->m_capacities.assign(this->m_graph_nodes + 1, aux);

    f >> number_edges;

    for(int i = 0; i < number_edges; i++){
        int x, y, z;

        f >> x >> y >> z;

        this->m_capacities[x][y] = this->m_capacities[x][y] + z;

        this->m_graph_adjacency_list[x].push_back(y);
        this->m_graph_adjacency_list[y].push_back(x);
    }
}

//ALGORITMI FUNDAMENTALI

vector<vector<int>> Graph::roy_floyd() {
    vector<vector<int>> path_matrix;
    vector<int> aux;

    aux.assign(this->m_graph_nodes + 1, 0);
    path_matrix.assign(this->m_graph_nodes + 1, aux);

    for(int i = 1; i <= this->m_graph_nodes; i++){

        for(int j = 1; j <= this->m_graph_nodes; j++){

            path_matrix[i][j] = this->m_costs_matrix[i][j];
        }
    }

    for(int k = 1; k <= this->m_graph_nodes; k++){

        for(int i = 1; i <= this->m_graph_nodes; i++){

            for(int j = 1; j <= this->m_graph_nodes; j++){

                    if(i != j && path_matrix[i][k] != 0 && path_matrix[k][j] != 0){

                        if(path_matrix[i][j] > path_matrix[i][k] + path_matrix[k][j]){

                            path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];

                        }else if (path_matrix[i][j] == 0){

                            path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];
                        }
                    }
            }
        }
    }

    return path_matrix;
}

int Graph::edmonds_karp() {
    int max_flow = 0;

    vector<vector<int>> flows;
    vector<int> tata;
    vector<int> viz;

    tata.assign(this->m_graph_nodes + 1, 0);
    flows.assign(this->m_graph_nodes + 1, tata);
    viz.assign(this->m_graph_nodes + 1, 0);

    while(this->minimum_length_BFS(flows, tata, viz) != 0){

        for(int i = 0; i < this->m_graph_adjacency_list[this->m_graph_nodes].size(); i++){

            int neighbor;

            neighbor = this->m_graph_adjacency_list[this->m_graph_nodes][i];

            if(flows[neighbor][this->m_graph_nodes] != this->m_capacities[neighbor][this->m_graph_nodes] && viz[neighbor] == 0){

                tata[this->m_graph_nodes] = neighbor;

                int min_flow = INT_MAX;
                for(int j = this->m_graph_nodes; j != 1; j = tata[j]){
                    if(min_flow > this->m_capacities[tata[j]][j] - flows[tata[j]][j]){
                        min_flow = this->m_capacities[tata[j]][j] - flows[tata[j]][j];
                    }
                }

                if(min_flow != 0){

                    for(int j = this->m_graph_nodes; j != 1; j = tata[j]){

                        flows[tata[j]][j] = flows[tata[j]][j] + min_flow;
                        flows[j][tata[j]] = flows[j][tata[j]] - min_flow;
                    }

                    max_flow = max_flow + min_flow;
                }
            }
        }
    }

    return max_flow;
}

//HELPERE

void Graph::print_path_matrix(vector<vector<int>> path_matrix, char *file) {

    ofstream out(file);

    for(int i = 1; i <= this->m_graph_nodes; i++){

        for(int j = 1; j <= this->m_graph_nodes; j++){
            out<<path_matrix[i][j]<<" ";
        }

        out<<"\n";
    }
}

//FUNCTII PRIVATE UTILE
int Graph::minimum_length_BFS(vector<vector<int>>& flows, vector<int>& tata, vector<int>& viz) {
    vector<int> cd;

    cd.assign(this->m_graph_nodes + 1, 0);

    cd[0] = cd[1] = 1;
    viz[1] = 1;

    for(int i = 1; i <= cd[0]; i++){
        int node;

        node = cd[i];
        if(node != this->m_graph_nodes){
            for(int j = 0; j < this->m_graph_adjacency_list[this->m_graph_nodes].size(); j++){

                int vecin;
                vecin = this->m_graph_adjacency_list[node][j];

                if(this->m_capacities[node][vecin] != flows[node][vecin] && viz[vecin] == 0){
                    viz[vecin] = 1;
                    cd[++cd[0]] = vecin;
                    tata[vecin] = node;
                }
            }
        }
    }

    return viz[this->m_graph_nodes];
}

int main() {

    //FLOYD WARSALL INFOARENA

    /*Graph g;
    g.read_graph_with_costs_as_costs_matrix("../royfloyd.in");

    vector<vector<int>> path_matrix;
    path_matrix = g.roy_floyd();
    g.print_path_matrix(path_matrix,"../royfloyd.out");*/

    //MAXFLOW INFOARENA

    ofstream out("../maxflow.out");
    Graph g;
    int max_flow;
    g.read_transport_routes("../maxflow.in");
    max_flow = g.edmonds_karp();
    out<<max_flow;
    return 0;
}