Month: 8 月 2006

最优匹配(Kuhn_Munkras算法)

Posted on by snoopy 
// ** Start of PerfectMatch *******************************
// Name: PerfectMatch by Kuhn_Munkras O(n^3)
// Description: w is the adjacency matrix, nx,ny are the size of x and y,
// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking
// whether the i-th node is visited, matx[x] means x match matx[x],
// maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays are start at 1

int nx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];
int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    fx[u]=1;
    for(v=1;v<=ny;v++)
        if((lx[u]+ly[v]==w[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((lx[u]...
    return(0);
} // end of int path()

int PerfectMatch()
{
    int ret=0,i,j,k,p;

    memset(ly,0,sizeof(ly));
    for(i=1;i<=nx;i++) {
        lx[i]=-INF;
        for(j=1;j<=ny;j++)
            if(w[i][j]>lx[i])
                lx[i]=w[i][j];
    } // end of for(i...

    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++) {
        memset(fx,-1,sizeof(fx));
        memset(fy,-1,sizeof(fy));
        if(!path(i)) {
            i--;
            p=INF;
            for(k=1;k<=nx;k++)
                if(fx[k]>0)
                    for(j=1;j<=ny;j++)
                        if((fy[j]<0)&&(lx[k]+ly[j]-w[k][j]<p))
                            p=lx[k]+ly[j]-w[k][j];
            for(j=1;j<=ny;j++) ly[j]+=(fy[j]<0?0:p);
            for(k=1;k<=nx;k++) lx[k]-=(fx[k]<0?0:p);
        } // end of if(!path(i))
    } // end of for(i...

    for(i=1;i<=ny;i++) ret+=w[maty[i]][i];
    return ret;
} // end of int PerfectMatch()
// ** End of PerfectMatch *********************************

最大匹配(匈牙利算法)

Posted on by snoopy 
// ** Start of MaximumMatch *******************************
// Name: MaximumMatch by Hungray O(n^3)
// Description: mat is the adjacency matrix, nx,ny are the size of x and y,
// fy is used for marking whether the k-th node is visited, matx[x] means x
// match matx[x], maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays start at 1

int nx,ny,mat[MAXN][MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    for(v=1;v<=ny;v++)
        if((mat[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((mat[u][v]...
    return(0);
} // end of int path()

int MaximumMatch()
{
    int i,ret=0;
    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++)
        if(matx[i]<0) {
            memset(fy,-1,sizeof(fy));
            ret+=path(i);
        } // end of if(matx[i]...
    return(ret);
} // end of int MaximumMatch()
// ** End of MaximumMatch *********************************