!Диниц с Масштабированием

#include <bits/stdc++.h>

using namespace std;

#define fastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define in(s) freopen(s, "r", stdin)
#define out(s) freopen(s, "w", stdout)

typedef long long ll;
typedef long double ld;

struct edge
{
    int a, b, f, w;
};

const int INF = 1e9 + 2;
const int MAXN = 502;

int n, m;
vector <edge> e;
int arr[MAXN];
vector <int> g[MAXN];
ll ans = 0;
int d[MAXN];
int lowest;

void func(int s, int t, int w)
{
    g[s].push_back((int)e.size());
    e.push_back({s, t, 0, w});

    g[t].push_back((int)e.size());
    e.push_back({t, s, 0, 0});
}

bool bfs()
{
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    d[1] = 0;
    queue<int> q;
    q.push(1);
    while (!q.empty() && d[n] == INF)
    {
        int v = q.front();
        q.pop();
        for (int i = 0; i < (int)g[v].size(); i++)
        {
            int id = g[v][i];
            int u = e[id].b;
            if (d[u] == INF && e[id].w - e[id].f >= lowest)
            {
                d[u] = d[v] + 1;
                q.push(u);
            }
        }
    }
    return d[n] != INF;
}

bool dfs(int v, int flow)
{
    if (!flow || v == n)
        return flow;
    for (; arr[v] < (int)g[v].size(); arr[v]++)
    {
        int id = g[v][arr[v]];
        int u = e[id].b;
        if (d[u] == d[v] + 1 && e[id].w - e[id].f >= flow)
            if (dfs(u, flow))
            {
                e[id].f += flow;
                e[id ^ 1].f -= flow;
                return flow;
            }
    }
    return 0;
}

int main()
{
    in("flow2.in");
    out("flow2.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        func(a, b, c);
    }
    for (lowest = (1 << 30); lowest >= 1;)
    {
        if (!bfs())
        {
            lowest >>= 1;
            continue;
        }
        for (int i = 1; i <= n; i++)
            arr[i] = 0;
        while (dfs(1, lowest))
            ans += lowest;
    }
    cout << ans << endl;
    return 0;
}