Минимальный срез. Алгоритм Диница (без масштабирования)

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;
typedef pair <int, int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;

const ll INF = 1e9 + 7;

struct Edge // 2-ой вариант представления ребер
{
    int u, v; // u -> v
    ll f, c; // поток и пропускная способность ребра

    int rev; // позиция обратного ребра (v -> u) в списке смежности
             // пример обращения: g[e.v][e.rev]

    Edge(int u, int v, ll c) : u(u), v(v), f(0), c(c) {}; // f = 0 т.к. изначально жижа не течет
};

int n, m;
vector <Edge> g[107];
int d[107], visited[107], first[107];

// DFS: АЛГОРИТМ ДИНИЦА (БЕЗ МАСШТАБИРОВАНИЯ)

ll DFS(int u, ll c)
{
    visited[u] = 1;

    if (u == n) return c;

    for (; first[u] < g[u].size(); ++first[u])
    {
        Edge e = g[u][first[u]];

        if (!visited[e.v] && (d[e.v] = d[u] + 1) && (e.c - e.f) > 0)
        {
            ll r = DFS(e.v, min(c, e.c - e.f));

            if (r > 0)
            {
                g[u][first[u]].f += r;
                g[e.v][e.rev].f -= r; // -r даже для неориентированного графа в силу св-в потока

                return r;
            }
        }
    }

    return 0;
}

// BFS: АЛГОРИТМ ДИНИЦА (БЕЗ МАСШТАБИРОВАНИЯ)

bool BFS()
{
    for (int i = 1; i <= n; ++i) d[i] = -1;

    queue <int> q;

    q.push(1); d[1] = 0;

    while (!q.empty())
    {
        int u = q.front(); q.pop();

        for (int j = 0; j < g[u].size(); ++j)
        {
            Edge e = g[u][j];

            if (d[e.v] == -1 && e.f < e.c)
            {
                q.push(e.v);

                d[e.v] = d[u] + 1;
            }
        }
    }

    return d[n] != -1; // мы достигли вершины t (t = n) или нет?
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    vii edges(m);

    for (int i = 0; i < m; ++i)
    {
        // нумерация вершин начинается с 1

        int u, v, c; cin >> u >> v >> c;

        Edge e = Edge(u, v, c);
        Edge inv_e = Edge(v, u, c); // обратим внимание что для неориентированного графа c != 0

        g[u].push_back(e);
        g[v].push_back(inv_e);

        g[u][g[u].size() - 1].rev = g[v].size() - 1;
        g[v][g[v].size() - 1].rev = g[u].size() - 1;

        edges[i] = { u, v };
    }

    // АЛГОРИТМ ДИНИЦА

    while (BFS())
    {
        for (int i = 1; i <= n; ++i) first[i] = 0;

        while (true)
        {
            for (int i = 1; i <= n; ++i) visited[i] = 0;

            ll r = DFS(1, INF);

            if (r == 0) break;
        }
    }

    for (int i = 1; i <= n; ++i) visited[i] = 0;

    // поиск минимального разреза

    queue <int> q;

    q.push(1); visited[1] = 1;

    while (!q.empty())
    {
        int u = q.front(); q.pop();

        for (int j = 0; j < g[u].size(); ++j)
        {
            Edge e = g[u][j];

            if (!visited[e.v] && e.f < e.c)
            {
                q.push(e.v);

                visited[e.v] = 1;
            }
        }
    }

    ll maxFlow = 0;

    for (int j = 0; j < g[1].size(); ++j)
        maxFlow += g[1][j].f;

    vi pos; // для ответа


    for (int i = 0; i < m; ++i)
    {
        int u = edges[i].first, v = edges[i].second;

        if (visited[u] != visited[v]) pos.push_back(i + 1);
    }

    cout << pos.size() << " " << maxFlow << "\n";

    for (int j = 0; j < pos.size(); ++j)
        cout << pos[j] << " ";

    return 0;
}