ford fulkerson

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define NMAX 1005

using namespace std;

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

vector<int> G[NMAX];
int C[NMAX][NMAX], p[NMAX];
bool viz[NMAX];

bool BFS(int s, int t, int n) {
    int x;
    queue<int> Q;

    memset(viz,0,sizeof(viz));

    Q.push(s);
    viz[s] = 1;
    p[s] = -1;

    while(!Q.empty()) {
        x = Q.front();
        Q.pop();

        for(int y=1;y<=n;++y) {
            if(!viz[y] && C[x][y] > 0) {
                Q.push(y);
                p[y] = x;
                viz[y] = 1;
            }
        }
    }

    return viz[t];
}

int main() {
    int n,m,i,x,y,c,nod;

    fin>>n>>m;
    for(i=1;i<=m;++i) {
        fin>>x>>y>>c;

        G[x].push_back(y);
        C[x][y] = c;
    }

    int flux = 0;
    while(BFS(1, n, n)) {
        int act_flux = INF;

        nod = n;
        while(nod != 1) {
            x = p[nod];
            act_flux = min(act_flux, C[x][nod]);

            nod = x;
        }

        nod = n;
        while(nod != 1) {
            x = p[nod];

            C[x][nod] -= act_flux;
            C[nod][x] += act_flux;

            nod = x;
        }

        flux += act_flux;
    }

    fout << flux;

    return 0;
}