[hdu2255]奔小康赚大钱(二分图最优匹配、KM算法)

题目大意：求二分图的最优匹配（首先数目最大， 其次权值最大）。

解题关键：KM算法

复杂度：$O(n^3)$

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<iostream>

#include<cmath>

using namespace std;

typedef long long ll;

const int N=;

const int inf=0x3f3f3f3f;

int nx,ny;

int g[N][N];

int match[N],lx[N],ly[N];//y中各点匹配状态，x,y中的顶点标号

int slack[N];

bool visx[N],visy[N];

bool hungry(int x){

    visx[x]=;

    for(int y=; y<=ny; y++){

        if(visy[y])continue;

        int tmp=lx[x]+ly[y]-g[x][y];

        if(tmp==){

            visy[y]=true;

            if(match[y]==- ||hungry(match[y])){

                match[y]=x;

                return ;

            }

        }

        else if(slack[y]>tmp) slack[y]=tmp;

    }

    return ;

}

int KM(){

    memset(match, -, sizeof match);

    memset(ly, , sizeof ly);

    for(int i=;i<=nx;i++){

        lx[i]=-inf;

        for(int j=;j<=ny;j++) lx[i]=max(lx[i],g[i][j]);

    }

    for(int x=;x<=nx;x++){

        for(int i=;i<=ny;i++) slack[i]=inf;

        while(){

            memset(visx,,sizeof visx);

            memset(visy,,sizeof visy);

            if(hungry(x))break;

            int d=inf;

            for(int i=;i<=ny;i++)if(!visy[i]&&d>slack[i]) d=slack[i];

            for(int i=;i<=nx;i++)if(visx[i])lx[i]-=d;

            for(int i=;i<=ny;i++){

                if(visy[i])ly[i]+=d;

                else slack[i]-=d;

            }

        }

    }

    int res=;

    for(int i=;i<=ny;i++)

        if(match[i]!=-) res+=g[match[i]][i];

    return res;

}

int main(){

    int n;

    while(~scanf("%d",&n)){

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                scanf("%d",&g[i][j]);

        nx=ny=n;

        printf("%d\n",KM());

    }

    return ;

}