匈牙利算法

· · 个人记录

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。

简介：

设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集V_1,V_2，选择这样的子集中边数最大的子集称为图的最大匹配问题(maximal matching problem)。

如果一个匹配中，|V_1|\le|V_2|且匹配数|M|=|V_1|，则称此匹配为完全匹配，也称作完备匹配。特别的当|V_1|=|V_2|称为完美匹配。

概念：

在介绍匈牙利算法之前还是先提一下几个概念，下面M是G的一个匹配。

若V=\left\{X_1,X_2,X_3,Y_1,Y_2,Y_3,Y_4\right\}，E=\left\{(X_1,Y_2),(X_1,Y_4),(X_2,Y_1),(X_2,Y_3),(X_3,Y_2)\right\}，其中边(X_1,Y_2),(X_2,Y_1)已经在匹配M上。

$M-$饱和点：对于$v\in V$，如果$v$与$M$中的某条边关联，则称$v$是$M-$饱和点，否则称$v$是非$M-$饱和点。如$X_1$,$X_2$,$Y_1$,$Y_2$都属于$M-$饱和点，而其它点都属于非$M-$饱和点。 $M-$可增广路：$p$是一条$M-$交错路，如果$p$的起点和终点都是非$M-$饱和点，则称$p$为$M-$可增广路。如$(X_3,Y_2,X_1,Y_4)$（不要和流网络中的增广路径弄混了）。 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。下面介绍用增广路求最大匹配的方法（称作匈牙利算法，匈牙利数学家$Edmonds$于$1965$年提出）。 增广路的定义（也称增广轨或交错轨）： 若$P$是图$G$中一条连通两个未匹配顶点的路径，并且属于$M$的边和不属于$M$的边（即已匹配和待匹配的边）在$P$上交替出现，则称$P$为相对于$M$的一条增广路径。 由增广路的定义可以推出下述三个结论： 1. $P$的路径个数必定为奇数，第一条边和最后一条边都不属于$M$。 1. 将$M$和$P$进行取反操作可以得到一个更大的匹配$M'$。 1. $M$为$G$的最大匹配当且仅当不存在$M$的增广路径。 算法轮廓： 1. 置$M$为空 1. 找出一条增广路径$P$，通过异或操作获得更大的匹配$M'$代替$M
  1. 重复2操作直到找不出增广路径为止

复杂度：

时间复杂度邻接矩阵：最坏为O(n^3)邻接表：O(nm)

空间复杂度 邻接矩阵：O(n^2)邻接表：O(n+m)

标程：

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>tu[1003];
bool bf[1003];
int match[1003];
int n,m,e,x,y,ans;
bool dfs(int pos) {
    for(register int i=0; i^tu[pos].size(); ++i) {
        if(!bf[tu[pos][i]]) {
            bf[tu[pos][i]]=1;
            if(!match[tu[pos][i]]) {
                match[tu[pos][i]]=pos;
                return 1;
            } else if(dfs(match[tu[pos][i]])) {
                match[tu[pos][i]]=pos;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    scanf("%d%d%d",&n,&m,&e);
    while(e--) {
        scanf("%d%d",&x,&y);
        if(x<=n&&y<=m) {
            tu[x].push_back(y);
        }
    }
    while(n) {
        memset(bf,0,sizeof(bf));
        if(dfs(n)) {
            ans++;
        }
        n--;
    }
    printf("%d",ans);
    return 0;
}