关于二分图的完美匹配问题

前言

占坑

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
using std::__gcd;
typedef long long ll;

template<typename T>
void read(T &x) {
    int flag = 1; x = 0; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}

const int N = 3e2 + 10, Inf = 1e9 + 7;
int n, w[N][N], match[N], ret;
int lx[N], ly[N];//定点标号
bool visx[N], visy[N];
void upt0(int &x, int y) { if(x < y) x = y; }
void upt1(int &x, int y) { if(x > y) x = y; }

bool Hungary(int x) {
    visx[x] = 1;
    for(int y = 1; y <= n; ++y) {
        if(!visy[y] && lx[x] + ly[y] == w[x][y]) {
            visy[y] = true;
            if(!match[y] || Hungary(match[y])) { match[y] = x; return 1; }
        } 
    } return 0;
}

int KM() {
    for(int i = 1; i <= n; ++i) {
        lx[i] = -Inf, ly[i] = 0;
        for(int j = 1; j <= n; ++j) upt0(lx[i], w[i][j]);
    }
    memset(match, 0, sizeof match);
    for(int x = 1; x <= n; ++x)
        while(1) {
            memset(visx, 0, sizeof visx), memset(visy, 0, sizeof visy);
            if(Hungary(x)) break;
            int inc = Inf;//增量标记
            for(int i = 1; i <= n; ++i)
                if(visx[i])
                    for(int j = 1; j <= n; ++j)
                        if(!visy[j]) upt1(inc, lx[i] + ly[j] - w[i][j]);
            for(int i = 1; i <= n; ++i) {
                if(visx[i]) lx[i] -= inc;
                if(visy[i]) ly[i] += inc;
            }
        }
    for(int i = 1; i <= n; ++i)
        if(match[i]) ret += w[match[i]][i];
    return ret;
}

int main () {
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                read(w[i][j]);
        printf("%d\n", KM()), ret = 0;
    }
    return 0;
}