Cod sursă (job #690199)

#include <bits/stdc++.h>
#include <unordered_map>
#include <map>

using namespace std;

ifstream fin("mincut.in");
ofstream fout("mincut.out");
//-----------------------------------------
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
//-----------------------------------------
#define f(i,s,e) for(int i=s;i<=e;++i)
#define nf(i,s,e) for(i=s;i<e;++i)
#define rf(i,e,s) for(i=e;i>=s;--i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sp <<" "
//------------------------------------------
const int NMAX = 1e3 + 20;
const int KMAX = 1e1 + 5;
const int MOD = 1e6 + 3;
const int INF = 0x3f3f3f3f;
//------------------------------------------
int n, m,t[NMAX];
vector<pair<int, int>>g[NMAX];
bitset<NMAX>viz;
vector<pair<int, int>>r[NMAX];
//------------------------------------------
void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        g[x].pb({ y,z });
    }
}
int bfs(int s, int d) {
    viz.reset();
    queue<int>q;
    q.push(s);
    viz[s] = 1;
    t[s] = -1;
    while (!q.empty()) {
        int nod = q.front();
        q.pop();
        for(auto x:r[nod])
            if (!viz[x.first] && x.second > 0) {
                q.push(x.first);
                t[x.first] = nod;
                viz[x.first] = 1;
            }
    }
    return (viz[d] == true);
}
void mincut(int s, int d) {
    int flux;
    for (int i = 1; i <= n; ++i)
        copy(g[i].begin(), g[i].end(), back_inserter(r[i]));
    while (bfs(s, d)) {
        flux = INT_MAX;
        for (int v = s; v != d; v = t[v]) {
            int nodd = t[v];
            if(nodd!=-1)
                flux = min(flux, r[nodd][v].second);
        }
        for (int v = s; v != d; v = t[v]) {
            int nodd = t[v];
            if (nodd != -1) {
                r[nodd][v].second -= flux;
                r[v][nodd].second += flux;
            }
        }
    }
    fout << flux;
}
void solve() {
    mincut(1, n);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    read();
    solve();
    return 0;
}