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)?'
':' ');
        REP(i,1,n+1) printf("%d%c",ly[i],(i==n)?'
':' ');
        int sum=0;
        REP(i,1,n+1) sum+=lx[i]+ly[i];
        printf("%d
",sum);
    }
    return 0;
}

UVA-11383 Golden Tiger Claw （KM算法）

相关推荐