二分图最优匹配.cpp

本人参加ACM竞赛使用的一些算法模板

/*
 *    Author         :   Jin Bin
 *    Description    :   KM algorithm in O(n^3) time
 *
 **********************************************************/
#include<cstdio>
#include<cstring>
#define maxn (1001)
long w[maxn][maxn],lx[maxn],ly[maxn],n;
// w[][] lx[] ly[] :-> 不会不知道吧!!!
long fx[maxn],fy[maxn],sy[maxn],slack[maxn],slackx[maxn];
// fx[] fy[] 记录增广路的父亲（左右）
// sy[]记录与右结点i 匹配的点
// slack[i](i为右边结点) Min(lx[j]+ly[i]-w[j][i]) (!visted[i]&&visited[j])
// slackx[i] 记录对应的j
void fix(long e){//从e开始增广
    while(e!=-1){
        sy[e]=fy[e];
        e=fx[fy[e]];
    }
}
long find(long s){
    long u,v,found,min;
    //初始化
    memset(fx,0,sizeof(fx));
    memset(fy,0,sizeof(fy));
    fx[s]=-1;
    for(u=1;u<=n;u++){
        slack[u]=lx[s]+ly[u]-w[s][u];
        slackx[u]=s;
    }
    while(1){
        found=0;
        for(u=1;u<=n;u++)//找一个slack[i]=0 这个点在当前lx,ly下可增广
            if(fy[u]==0&&slack[u]==0){
                found=1;
                if(sy[u]==0){//找到增广路
                    fy[u]=slackx[u];
                    return u;//返回
                }else{
                    fy[u]=slackx[u];//记下父亲
                    fx[sy[u]]=u;//再加匹配的点
                    for(v=1;v<=n;v++)//从儿子（左）更新slack[] slackx[]
                        if(fy[v]==0&&lx[sy[u]]+ly[v]-w[sy[u]][v]<slack[v]){
                            slack[v]=lx[sy[u]]+ly[v]-w[sy[u]][v];
                            slackx[v]=sy[u];
                        }//复杂度分析：每个左结点都进行一次Updata Slack[] O(n^2)
                }
            }
        if(!found){//没找到lx[i]+=delta;ly[j]-=delta;slack[j]-=delta;  v[i] !v[j]
                   //delta= min (slack[j])
                   //至少有一个 slack[j]-->0
            min=0x7fffffff;
            for(u=1;u<=n;u++)
                if(fy[u]==0)
                    min<?=slack[u];
            for(u=1;u<=n;u++){
                if(fx[u])
                    lx[u]-=min;
                if(fy[u])
                    ly[u]+=min;
                slack[u]-=min;
            }
        }//复杂度分析：每次修改lx[] ly[] slack[] 都至少增广两个顶点
        // 最多 n次修改lx[] ly[] slack[] 每次 O(n) 共O(n^2)
    }
}//本过程 O(n^2)
void init(){
    memset(sy,0,sizeof(sy));
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    scanf("%ld\n",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%ld",&w[i][j]);
            lx[i]>?=w[i][j];
        }
}
void KM(){
    for(int i=1;i<=n;i++)
        fix(find(i));//总共O(n^3)
}
void out(){
    long i,j,s=0;
    for(i=1;i<=n;i++)
        s+=w[sy[i]][i];
    printf("%ld\n",s);
}
int main(){
    init();
    KM();
    out();
    return 0;
}
/*
下面简述一般KM O(n^4)的原因：
共n次增广
每次增广 最多 n次修改lx[] ly[]
         ^^^^
每次修改lx[],ly[] O(n^2)  成为瓶颈
总计O(n^4)
而用了slack实际上是在从左端点尝试右端点时记下slack[] (时间没多画)
从而加速更新 lx[] ly[] slack[]
只是在一般情况下不需要n次修改lx[] ly[]
即每次修改lx[]ly[]可增广>=2个结点。
如果采用随机实数确保每次lx[]ly[]只增广2个结点。
那我的程序优势就很明显了!!!
*/