UVA-11383 Golden Tiger Claw （KM算法）

题目大意：一张可行二分图的权值以邻接矩阵的形式给了出来，现在要找每一个节点的可行顶标，使顶标和最小。

题目分析：直接用KM算法，结束后顶标之和最小。。。模板题。

代码如下：

# include<iostream>

# include<cstdio>

# include<queue>

# include<cmath>

# include<vector>

# include<cstring>

# include<algorithm>

using namespace std;

# define LL long long

# define REP(i,s,n) for(int i=s;i<n;++i)

# define CL(a,b) memset(a,b,sizeof(a))

# define CLL(a,b,n) fill(a,a+n,b)

const int N=505;

const int INF=1<<30;

int w[N][N],lx[N],ly[N],n;

int link[N],visx[N],visy[N],slack[N];

bool match(int x)

{

    visx[x]=1;

    REP(y,1,n+1){

        if(visy[y]) continue;

        int t=lx[x]+ly[y]-w[x][y];

        if(t==0){

            visy[y]=1;

            if(link[y]==-1||match(link[y])){

                link[y]=x;

                return true;

            }

        }else if(slack[y]>t)

            slack[y]=t;

    }

    return false;

}

void update()

{

    int d=INF;

    REP(i,1,n+1) if(!visy[i])

        d=min(d,slack[i]);

    REP(i,1,n+1) if(visx[i]) lx[i]-=d;

    REP(i,1,n+1){

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

        else slack[i]-=d;

    }

}

void KM()

{

    CL(link,-1);

    CL(ly,0);

    REP(i,1,n+1){

        lx[i]=-1;

        REP(j,1,n+1)

            lx[i]=max(lx[i],w[i][j]);

    }

    REP(x,1,n+1){

        CLL(slack,INF,n+1);

        while(1){

            CL(visx,0);

            CL(visy,0);

            if(match(x)) break;

            update();

        }

    }

}

int main()

{

    int T=15;

    while(T--)

    {

        scanf("%d",&n);

        REP(i,1,n+1) REP(j,1,n+1) scanf("%d",&w[i][j]);

        KM();

        REP(i,1,n+1) printf("%d%c",lx[i],(i==n)?'\n':' ');

        REP(i,1,n+1) printf("%d%c",ly[i],(i==n)?'\n':' ');

        int sum=0;

        REP(i,1,n+1) sum+=lx[i]+ly[i];

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

    }

    return 0;

}