lessons/参考实现/07-二分图/HDU-2255.cpp

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        vector<vector<long long>> weight(n, vector<long long>(n));
        for (auto &row : weight) for (auto &x : row) cin >> x;
        vector<long long> lx(n), ly(n, 0), slack(n);
        vector<int> match_y(n, -1);
        for (int x = 0; x < n; ++x) lx[x] = *max_element(weight[x].begin(), weight[x].end());

        for (int root = 0; root < n; ++root) {
            fill(slack.begin(), slack.end(), numeric_limits<long long>::max() / 4);
            while (true) {
                vector<bool> seen_x(n, false), seen_y(n, false);
                auto augment = [&](auto &&self, int x) -> bool {
                    seen_x[x] = true;
                    for (int y = 0; y < n; ++y) if (!seen_y[y]) {
                        long long gap = lx[x] + ly[y] - weight[x][y];
                        if (gap == 0) {
                            seen_y[y] = true;
                            if (match_y[y] == -1 || self(self, match_y[y])) {
                                match_y[y] = x; return true;
                            }
                        } else slack[y] = min(slack[y], gap);
                    }
                    return false;
                };
                if (augment(augment, root)) break;
                long long delta = numeric_limits<long long>::max() / 4;
                for (int y = 0; y < n; ++y) if (!seen_y[y]) delta = min(delta, slack[y]);
                for (int x = 0; x < n; ++x) if (seen_x[x]) lx[x] -= delta;
                for (int y = 0; y < n; ++y) {
                    if (seen_y[y]) ly[y] += delta;
                    else slack[y] -= delta;
                }
            }
        }
        long long answer = 0;
        for (int y = 0; y < n; ++y) answer += weight[match_y[y]][y];
        cout << answer << '\n';
    }
}