Hungarian Algorithm

#include <bits/stdc++.h>
#define sz(a) ((int)((a).size()))

using namespace std;
typedef long long ll;

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> l(n, 0), r(n, 0);
    vector<int> pairl(n, -1), pairr(n, -1);
    const int INF = 1e9 + 7;
    for (int iter = 0; iter < n; iter++) {
        int v = 0;
        while (pairl[v] != -1) {
            v++;
        }
        vector<int> usedl(n, 0), usedr(n, 0);
        vector<int> prev(n, -1);
        usedl[v] = 1;
        vector<pair<int, int>> w(n);
        for (int j = 0; j < n; j++) {
            w[j] = {a[v][j] + l[v] + r[j], v};
        }
        while (true) {
            pair<pair<int, int>, int> opt = {{INF, -1}, -1};
            for (int j = 0; j < n; j++) {
                if (!usedr[j]) {
                    opt = min(opt, {w[j], j});
                }
            }
            int curl = opt.first.second, curr = opt.second, x = opt.first.first;
            for (int i = 0; i < n; i++) {
                if (!usedl[i]) {
                    l[i] += x;
                }
            }
            for (int j = 0; j < n; j++) {
                if (!usedr[j]) {
                    r[j] -= x;
                    w[j].first -= x;
                }
            }
            prev[curr] = curl;
            if (pairr[curr] == -1) {
                while (curr != -1) {
                    int nxt = pairl[prev[curr]];
                    pairl[prev[curr]] = curr;
                    pairr[curr] = prev[curr];
                    curr = nxt;
                }
                break;
            }
            usedl[pairr[curr]] = 1;
            usedr[curr] = 1;
            for (int j = 0; j < n; j++) {
                w[j] = min(w[j], {a[pairr[curr]][j] + l[pairr[curr]] + r[j], pairr[curr]});
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i][pairl[i]];
    }
    cout << ans << '\n';
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ' ' << pairl[i] + 1 << '\n';
    }
}