二分图最优匹配模板题

#include<stdio.h>
#include<cstring>
#include<iostream>

using namespace std;
#define INF 0x3f3f3f3f
const int N = 510;
int graph[N][N],stx[N],sty[N],lx[N],ly[N],match[N],slack[N],n;

bool find(int i){
    int res = 0;
    stx[i] = 1;
    for(int j = 0 ; j < n ; j ++){
        if(sty[j]) continue;
        int temp = lx[i] + ly[j] - graph[i][j];
        if(temp == 0){
            sty[j] = 1;
            if(match[j] == -1 || find(match[j])){
                match[j] = i;
                return true;
            }
        }else{
            slack[j] = min(slack[j],temp);
        }
    }
    return false;
}

int KM(){
    int res = 0;
    for(int i = 0 ; i < n ; i ++){
        lx[i] = graph[i][0];
        for(int j = 1 ; j < n ; j ++)
            lx[i] = max(lx[i],graph[i][j]);
    }
    memset(match,-1,sizeof(match));
    for(int k = 0 ; k < n ; k ++){
        memset(slack,0x3f,sizeof(slack));        
        while(true){
            memset(stx,0,sizeof(stx));
            memset(sty,0,sizeof(sty));
            if(find(k)){
                break;
            }else{
                int delta = INF;
                for(int j = 0 ; j < n ; j ++)
                    if(sty[j] == 0)
                        delta = min(delta,slack[j]);
                for(int j = 0 ; j < n ; j ++){
                    if(stx[j]) lx[j] -= delta;
                    if(sty[j]) ly[j] += delta;
                    else slack[j] -=delta;
                }
            }
        }
    }
    for(int j = 0 ; j < n ; j ++)
        res += graph[match[j]][j];
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < n ; j ++)
            scanf("%d",&graph[i][j]);
    int res_max = KM();
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < n ; j ++)
            graph[i][j] = -graph[i][j];
    int res_min = -KM();
    printf("%d\n%d",res_min,res_max);
}