hdu 2255 二分图最大权匹配 km算法模板

代码是打的kuangbin的模板

注意km算法的复杂度是nx*nx*ny,所以当nx>ny的时候，将图行和列反转过来，不然有些题可能会TLE。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn= 305;
const int inf= 0x3f3f3f3f;
int g[maxn][maxn];
int nx,ny;//二分图两类点的个数
int linker[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool visx[maxn], visy[maxn];

bool dfs(int x)
{
    visx[x]=true;
    for(int y=0; y<ny; y++)
    {
        if(visy[y]) continue;
        int tmp=lx[x]+ly[y]-g[x][y];
        if(tmp==0){
            visy[y]=true;
            if(linker[y]==-1 || dfs(linker[y])){
                linker[y]=x;
                return true;
            }
        }
        else if(slack[y]>tmp)
            slack[y]=tmp;
    }
    return false;
}

int km()
{
    memset(linker, -1, sizeof(linker));
    memset(ly, 0, sizeof(ly));
    for(int i=0; i<nx; i++){
        lx[i]=-inf;
        for(int j=0;j<ny;j++)
            if(g[i][j]>lx[i])
                lx[i]=g[i][j];
    }

    for(int x=0; x<nx; x++){
        for(int i=0; i<ny; i++)
            slack[i]=inf;
        while(true){
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            if(dfs(x)) break;
            int d=inf;
            for(int i=0; i<ny; i++)
                if(!visy[i]&&d>slack[i])
                d=slack[i];
            for(int i=0; i<nx;i++)
                if(visx[i])
                lx[i]-=d;
            for(int i=0; i<ny; i++)
                if(visy[i]) ly[i]+=d;
            else slack[i]-=d;
        }
    }

    int res=0;
    for(int i=0; i<ny; i++)
        if(linker[i]!=-1)
            res+=g[linker[i]][i];
    return res;
}

int main()
{
    while(scanf("%d", &nx)==1){
        ny=nx;
        for(int i=0; i<nx; i++)
            for(int j=0; j<ny; j++)
            scanf("%d", &g[i][j]);
        printf("%d\n", km());
    }
}