TEAMBOOK min-cost-max-flow (задача о назначениях)

#include <bits/stdc++.h>
using long_type = long long;
#define long long_type
#define all(x) begin(x), end(x)
using namespace std;
mt19937 rnd;

struct edge {
    int v, u, c, f, w, r;
    edge(int _v, int _u, int _c, int _w, int _r) :
        v(_v),
        u(_u),
        c(_c),
        f(0),
        w(_w),
        r(_r) {}
};

const int max_n     = 604;
const int source    = max_n - 1;
const int sink      = max_n - 2;
const int inf       = 0x3f3f3f3f;

vector<edge> g[max_n];

void add_edge(int v, int u, int c, int w) {
    g[v].emplace_back(v, u, c, w, (int)g[u].size());
    g[u].emplace_back(u, v, 0, -w, (int)g[v].size() - 1);
}

int dist[max_n];
edge *par[max_n];
bool used[max_n];

void fb(int lim) {
    fill(all(dist), inf);
    fill(all(par), nullptr);
    fill(all(used), false);
    dist[source] = 0;
    deque<int> q;
    q.push_back(source);
    used[source] = true;

    while (q.size()) {
        int v = q.front();
        q.pop_front();
        used[v] = false;
        for (edge &e : g[v]) {
            if (e.c - e.f < lim) {
                continue;
            }
            if (dist[e.u] > dist[v] + e.w) {
                dist[e.u] = dist[v] + e.w;
                par[e.u]  = &e;
                if (!used[e.u]) {
                    used[e.u] = true;
                    int fr = inf;
                    if (q.size()) {
                        fr = dist[q.front()];
                    }
                    if (dist[e.u] < fr) {
                        q.push_front(e.u);
                    } else {
                        q.push_back(e.u);
                    }
                }
            }
        }
    }
}

vector<edge *> path;

void rec_path() {
    path.clear();
    int v = sink;
    while (v != source) {
        assert(par[v]);
        path.push_back(par[v]);
        assert(v == par[v]->u);
        v = par[v]->v;
    }
    reverse(all(path));
}

long mcmf() {
    long answer = 0;
    while (1) {
        fb(1);
        if (dist[sink] == inf) {
            break;
        }
        rec_path();
        int min_cap = inf;
        long sum    = 0;
        for (edge *ep : path) {
            min_cap = min(min_cap, ep->c - ep->f);
            sum += ep->w;
        }
        answer += sum * min_cap;
        for (edge *ep : path) {
            edge &e = *ep;
            edge &r = g[e.u][e.r];
            e.f += min_cap;
            r.f -= min_cap;
            assert(e.f <= e.c);
            assert(r.f <= r.c);
        }
    }
    return answer;
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
#define TASK "assignment"
    assert(freopen(TASK ".in", "r", stdin));
    assert(freopen(TASK ".out", "w", stdout));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int c;
            cin >> c;
            add_edge(i, n + j, 1, c);
        }
    }
    for (int i = 1; i <= n; ++i) {
        add_edge(source, i, 1, 0);
        add_edge(n + i, sink, 1, 0);
    }
    cout << mcmf() << "\n";
    vector<pair<int, int>> answer;
    for (int i = 1; i <= n; ++i) {
        for (edge e : g[i]) {
            if (e.f == 1) {
                answer.emplace_back(i, e.u - n);
            }
        }
    }
    for (auto e : answer) {
        cout << e.first << " " << e.second << "\n";
    }
    cerr << "time = " << 1000 * clock() / CLOCKS_PER_SEC << endl;
    return 0;
}