KM算法学习笔记

学习笔记 二分图

目录

• KM算法学习笔记
  • 最佳完美匹配
    • 某个不知名的定理
  • 算法实现
    • 可行顶标与松弛变量
    • 代码
  • 练习
    • [HDU 2255] 奔小康赚大钱
    • [UVa 11383] Golden Tiger Claw

最佳完美匹配

对于一个有完美匹配的二分图，将其中的边都赋了一个边权（可以为负），其中边权和最大的完美匹配叫做该二分图的最佳完美匹配。

某个不知名的定理

一些约定：

1. 这里讨论的二分图都指有完美匹配的二分图；
2. 记二分图左边的点集为$X$，右边的为$Y$；
3. 连接$u \in X,v \in Y$的边记为$(u,v)$，其权值记为$w(u,v)$；
4. 形如$lx(u)$的都是对于某个点$u$而言的一些值。
5. 对于一个二分图的两个点集，我们给每个点分配一个顶标，记为$lx(u),u \in X$或$ly(v),v \in Y$；

定理：

• 一组$\{ lx(u)\mid u \in X \},\{ ly(v)\mid v \in Y \}$是合法的$\iff$该二分图中任意的边$(u,v)$都满足$w(u,v) \leq lx(u)+ly(v)$；
• 我们称对于一组合法的$lx,ly$，若一条边$(u,v)$满足$w(u,v)=lx(u)+ly(v)$，则称其为可行边，所有可行边构成的子图称为相等子图；
• 若该相等子图存在完美匹配，且该完美匹配就是该二分图的最佳完美匹配；
• 证明：
  
  • 记$sum(G)$为某个完美匹配子图的边权和，最佳完美匹配子图为$G^*$；
  • 则$sum(G^*)= \sum_{u \in X} lx(u) + \sum_{v \in Y} ly(v)$；
  • 而根据$lx,ly$的合法性要求，对于任意的完美匹配子图，有$sum(G) \leq \sum_{u \in X} lx(u) + \sum_{v \in Y} ly(v)$；
  • 所以$G^*$为该二分图的最佳完美匹配。

算法实现

可行顶标与松弛变量

• 考虑顶标可行的初值，显然$lx(u)= \max_{v \in Y} \{ w(u,v) \},ly(v)=0$是可行的，那么就不妨设其为初值；
• 但这样的一组$lx,ly$的相等子图不一定有完美匹配，我们考虑在不影响其可行性的前提下逐步调整$lx,ly$；
• 赋完初值后，我们正常的跑匈牙利算法，但只走可行边；
• 对于一个点$u \in X$，如果能匹配上就继续下一个，不然我们就要考虑调整顶标，使更多的边变成可行边了；
• 记$X',Y'$分别为$X$中和$Y$中未匹配上的点的点集，则显然所有可行边中：$\nexists (u,v),u \in X',v \in Y'$（因为当前已经不能继续匹配了），而$\forall (u,v),u \in X',v \in Y$都是非匹配边；
• 考虑将$\forall u \in \complement_{X}X',lx(u)-=d$，并且$\forall v \in \complement_{Y}Y',ly(v)+=d$，则所有匹配边仍然可行，非匹配边则变得不可行，而不可行边可能进入相等子图。证明：
  
  1. 对于任意一条匹配边$(u,v)$，有$u \in X,v \in Y$且$w(u,v)=lx(u)+ly(v)$，显然$lx(u)-d+ly(v)+d$仍等于$w(u,v)$。故匹配边的可行性不变；
  2. 对于任意一条非匹配边$(u,v)$，有$u \in X',v \in Y$且$w(u,v)=lx(u)+ly(v)$，那么$lx(u)+ly(v)+d \gt lx(u)+ly(v)=w(u,v)$。故非匹配边变成了不可行边；
  3. 对于任意一条不可行边$(u,v)$，有$u \in X,v \in Y'$且$w(u,v) < lx(u)+ly(v)$，则$lx(u)-d+ly(v) \lt lx(u)+ly(v)$，可能等于$w(u,v)$。故不可行边可能进入相等子图。
• 不难发现，$d= \min_{u \in X,v \in Y'} \{lx(u)+ly(v)-w(u,v) \}$；
• 如果考虑每次匹配失败后暴力修改，则需要$O(n^2)$的时间来求$d$；
• 但如果给$\forall v \in Y$定义一个松弛变量$slack(v)= \min_{u \in X} \{lx(u)+ly(v)-w(u,v)\}$，则$d= \min_{v \in Y'} \{slack(v)\}$，只需要$O(n)$的时间即可完成修改了；
• 考虑对于每个$X$中的点都要增广一次去匹配，每次匹配最坏要遍历整个二分图，若匹配失败则最多需要修改$n$次顶标，故KM算法总复杂度为$O(n^3)$。

代码

int n;
int G[MAXN][MAXN],lx[MAXN],ly[MAXN],slack[MAXN],match[MAXN];
bool visx[MAXN],visy[MAXN];
bool Hungary(int x){
    visx[x]=true;
    for(int y=1,dta;y<=n;++y){
        dta=lx[x]+ly[y]-G[x][y];
        if(!visy[y] && dta==0){
            visy[y]=true;
            if(!match[y] || Hungary(match[y])){
                match[y]=x;
                return true;
            }
        }
        else slack[y]=min(slack[y],dta);
    }
    return false;
}
inline int KM(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            lx[i]=max(lx[i],G[i][j]);
    }
    for(int x=1,d;x<=n;++x){
        memset(visx,false,sizeof(visx));
        memset(visy,false,sizeof(visy));
        memset(slack,0x7f,sizeof(slack));
        while(!Hungary(x)){
            d=INT_MAX;
            for(int y=1;y<=n;++y){
                if(!visy[y]) d=min(d,slack[y]);
            }
            for(int i=1;i<=n;++i){
                if(visx[i]){
                    lx[i]-=d;
                    visx[i]=false;
                }
                if(visy[i]){
                    ly[i]+=d;
                    visy[i]=false;
                }
            }
        }
    }
    int ret=0;
    for(int i=1;i<=n;++i)
        ret+=lx[i]+ly[i];
    return ret;
}

练习

[HDU 2255] 奔小康赚大钱

• 裸模板。。。

代码：

#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>
using std::min;
using std::max;
const int MAXN=305;
int n;
int lx[MAXN],ly[MAXN],G[MAXN][MAXN],slack[MAXN],match[MAXN];
bool visx[MAXN],visy[MAXN];
bool Hungary(int x){
    visx[x]=true;
    for(int y=1,dta;y<=n;++y){
        dta=lx[x]+ly[y]-G[x][y];
        if(!visy[y] && dta==0){
            visy[y]=true;
            if(!match[y] || Hungary(match[y])){
                match[y]=x;
                return true;
            }
        }
        else slack[y]=min(slack[y],dta);
    }
    return false;
}
inline int KM(){
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(match,0,sizeof(match));
    for(int x=1;x<=n;++x){
        for(int y=1;y<=n;++y)
            lx[x]=max(lx[x],G[x][y]);
    }
    for(int x=1,d;x<=n;++x){
        memset(slack,0x7f,sizeof(slack));
        memset(visx,false,sizeof(visx));
        memset(visy,false,sizeof(visy));
        while(!Hungary(x)){
            d=INT_MAX;
            for(int y=1;y<=n;++y){
                if(!visy[y]) d=min(d,slack[y]);
            }
            for(int i=1;i<=n;++i){
                if(visx[i]){
                    lx[i]-=d;
                    visx[i]=false;
                }
                if(visy[i]){
                    ly[i]+=d;
                    visy[i]=false;
                }
            }
        }
    }
    int ret=0;
    for(int i=1;i<=n;++i)
        ret+=lx[i]+ly[i];
    return ret;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j)
                scanf("%d",&G[i][j]);
        }
        printf("%d\n",KM());
    }
    return 0;
}

[UVa 11383] Golden Tiger Claw

• 看到行列很容易想到构建二分图进行匹配；
• 但是$w(i,j) \leq row(i)+col(j)$怎么办呢？
• 考虑KM算法中的不等式$lx(u)+ly(v) \geq w(u,v)$对于任意边都满足，而最佳完美匹配子图有$lx(u)+ly(v)=w(u,v)$，所以最佳完美匹配子图的顶标之和是最小的，即为答案。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using std::min;
using std::max;
const int MAXN=505;
int n;
int G[MAXN][MAXN],lx[MAXN],ly[MAXN],slack[MAXN],match[MAXN];
bool visx[MAXN],visy[MAXN];
bool Hungary(int x){
    visx[x]=true;
    for(int y=1,dta;y<=n;++y){
        dta=lx[x]+ly[y]-G[x][y];
        if(!visy[y] && dta==0){
            visy[y]=true;
            if(!match[y] || Hungary(match[y])){
                match[y]=x;
                return true;
            }
        }
        else slack[y]=min(slack[y],dta);
    }
    return false;
}
inline int KM(){
    memset(lx,-0x7f,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            lx[i]=max(lx[i],G[i][j]);
    }
    for(int x=1,d;x<=n;++x){
        memset(visx,false,sizeof(visx));
        memset(visy,false,sizeof(visy));
        memset(slack,0x7f,sizeof(slack));
        while(!Hungary(x)){
            d=INT_MAX;
            for(int y=1;y<=n;++y){
                if(!visy[y]) d=min(d,slack[y]);
            }
            for(int i=1;i<=n;++i){
                if(visx[i]){
                    lx[i]-=d;
                    visx[i]=false;
                }
                if(visy[i]){
                    ly[i]+=d;
                    visy[i]=false;
                }
            }
        }
    }
    int ret=0;
    for(int i=1;i<=n;++i)
        ret+=lx[i]+ly[i];
    return ret;
}
int main(){
    int ans;
    while(scanf("%d",&n)!=EOF){
        memset(G,0,sizeof(G));
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j)
                scanf("%d",&G[i][j]);
        }
        ans=KM();
        for(int i=1;i<=n;++i)
            printf("%d ",lx[i]);
        putchar('\n');
        for(int i=1;i<=n;++i)
            printf("%d ",ly[i]);
        putchar('\n');
        printf("%d\n",ans);
    }
    return 0;
}