// a) https://www.infoarena.ro/problema/maxflow
/*
    Flux maxim
        O retea de transport este un graf orientat in care fiecare muchie are asociata o capacitate si o anumita cantitate de flux. Fluxul primit de fiecare muchie trebuie sa fie mai mic
     sau egal decat capacitatea acesteia. De asemenea, pentru fiecare nod, fluxul care intra in nod trebuie sa fie egal cu cantitatea de flux care iese din nod. Cu alte cuvinte, suma fluxurilor asociate 
     muchiilor care intra intr-un nod trebuie sa fie egala cu suma fluxurilor asociate muchiilor care ies din nod, exceptie facand nodurile speciale S si D, denumite sursa, respectiv, destinatie. Din 
     nodul sursa poate doar iesi flux, in timp ce in nodul destinatie poate doar intra flux. Valoarea fluxului unei astfel retele este egal cu suma fluxului care iese din sursa sau cu suma fluxului care 
     intra in destinatie (cele doua fluxuri sunt egale).

    Cerinta 
        Dandu-se o retea de transport, in care initial fluxul pe fiecare muchie este 0, sa se calculeze fluxul maxim care poate fi trimis prin aceasta retea.

    Date de intrare
        Fisierul de intrare maxflow.in va contine pe prima linie 2 numere, N si M, reprezentand numarul de noduri si numarul de muchii din retea. Pe fiecare din urmatoarele M linii, se vor
    afla cate 3 numere naturale, x, y si z, cu semnificatia ca exista o muchie care porneste de la nodul x, ajunge in nodul y si are capacitatea z.

    Date de ieşire
        In fisierul de iesire maxflow.out se va afla un singur numar F, reprezentand fluxul maxim ce poate fi trimis prin retea.
*/

/*
    b) Modificați algoritmul de la punctul a) astfel încât să afișați tăietura minima între sursa și orice alt vârf, adică o mulțime de arce cu costul total minim pe care dacă le eliminăm din rețea cel
    puțin un vârf care era accesibil inițial din sursă după eliminare nu mai este accesibil.
*/


#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

ifstream fin("maxflow.in"); 
ofstream fout("maxflow.out"); 

int nrNoduri, nrMuchii;
vector<vector<int>> listaAdiacenta, grafRezidual, graf; 

//functia in cadrul careia sunt citite datele:
//arcele grafului initial sunt memorate intr-o lista de adiacenta
//graful rezidual este memorat intr-o matrice de adiacenta (adiacenta nodurilor este caracterizata de capacitatea reziduala)
void citire()
{
    fin >> nrNoduri >> nrMuchii; 

    listaAdiacenta.resize(nrNoduri + 1); 
    grafRezidual.resize(nrNoduri + 1, vector<int>(nrNoduri + 1, 0)); 
    graf.resize(nrNoduri + 1, vector<int>(nrNoduri + 1, 0));

    int nodIntrare, nodIesire, capacitate; 
    for (int i = 0; i < nrMuchii; i++)
    {
        fin >> nodIntrare >> nodIesire >> capacitate; 

        listaAdiacenta[nodIntrare].push_back(nodIesire); 
        listaAdiacenta[nodIesire].push_back(nodIntrare); 

        graf[nodIntrare][nodIesire] = 1; 

        grafRezidual[nodIntrare][nodIesire] = capacitate; 

    }

}

vector<bool> vizitat; 
vector <int> tata; 

//in cadrul parcurgerii BFS caut lanturi de la nodul de inceput (nodul 1) la nodul final (nodul nrNoduri) in care fiecare muchie sa aiba capacitatea reziduala mai mica decat capacitatea initiala
bool BFS()
{
    queue<int> vecini;

    tata.clear(); 
    tata.resize(nrNoduri + 1, 0); 

    vizitat.clear(); 
    vizitat.resize(nrNoduri + 1, false); 

    vecini.push(1); 
    vizitat[1] = true; 
    while (!vecini.empty())
    {
        int nodCurent = vecini.front(); 
        vecini.pop(); 

        if (nodCurent == nrNoduri) //am ajuns la nodul de sfasit, asadar am gasit un lant care respecta criteriile impuse, deci ies din structura repetitiva
            continue; 

        for(int vecin : listaAdiacenta[nodCurent])
            if (!vizitat[vecin] && grafRezidual[nodCurent][vecin] > 0)
            {
                tata[vecin] = nodCurent;
                vecini.push(vecin); 
                vizitat[vecin] = true; 
            }
    }

    return vizitat[nrNoduri]; 
}

//algoritmul edmonds-karp: 
void EdmondsKarp()
{
    int fluxMaxim = 0; 

    //pentru gasirea drumurilor de ameliorare (drum de la sursa la destinatie, in care fiecare muchie de pe drum sa aiba fluxul asociat pana in acest moment strict mai mic decat capacitatea sa) folosesc parcurgere BFS
    //cat timp exista astfel de drumuri de ameliorare, le parcurg, adaugand flux
    while (BFS())
    {
        //penrtu fiecare drum de ameliorare gasit, caut bottleneck-ul (valoarea minima cu care poate fi marit fluxul asociat fiecarei muchii care se afla pe drumul gasit) si updatez capacitatile reziduale 
        for (int vecin : listaAdiacenta[nrNoduri])
        {
            if (vizitat[vecin] && grafRezidual[vecin][nrNoduri] > 0)
            {
                int fluxCrt = grafRezidual[vecin][nrNoduri]; 
                for (int nodCrt = vecin; nodCrt != 1; nodCrt = tata[nodCrt])
                    fluxCrt = min(fluxCrt, grafRezidual[tata[nodCrt]][nodCrt]); 

                grafRezidual[vecin][nrNoduri] -= fluxCrt; 
                grafRezidual[nrNoduri][vecin] += fluxCrt;
                for (int nodCrt = vecin; nodCrt != 1; nodCrt = tata[nodCrt])
                {
                    grafRezidual[tata[nodCrt]][nodCrt] -= fluxCrt;
                    grafRezidual[nodCrt][tata[nodCrt]] += fluxCrt;
                }

                fluxMaxim += fluxCrt; 
            }
        }
    }

    fout << fluxMaxim << "\n"; 
}


int main()
{
    citire(); 

    //a) pentru a rezolva aceasta problema putem folosi algoritmul Edmonds-Karp pentru aflarea fluxului maxim 
    EdmondsKarp(); 
}