二分图匹配相关算法

$$二分图匈牙利算法$$
这里简单记录下二分图匹配的相关算法，供自己使用。如果各位游客看到觉得浪费时间，便请移步，文章全为个人模板记录

• 匈牙利算法
  匈牙利算法研究的是二分图的最大匹配，是对给定的二分图求得最大的满足条件的匹配数，匹配对。其算法思想是利用Berge定理和Hall定理将初始匹配通过迭代寻找增广路径得到最大匹配，每次迭代得到的匹配大小加1
  具体迭代实现有DFS和BFS两种。下面贴上DFS版的cpp写法
  时间复杂度O($n\times m$)
  
  
  

//匈牙利算法 时间复杂度为O(n*m) #include "bits/sdtc++.h" #define MAX 1003 using namespace std; int n,m,e; int map[MAX][MAX]; int vis[MAX]; int nextLeft[MAX],nextRight[MAX];//nextLeft[]是左部点匹配到右边的点，同理nextRight int fa[MAX]; bool Find(int u) { 
    //是DFS迭代寻找增广路径，(还有个形象的说法就是腾地) for (int i = 1; i<= m; i++) { 
    if (map[u][i] && !vis[i]) { 
    vis[i] = 1; if (-1==nextRight[i] || Find(nextRight[i])) { 
    //“腾地”，如果，nextRight[i]还未匹配右边的点，或者nextRight[i]还有增广路径可走有其他点可以与其匹配就“腾地” nextRight[i] = u; nextLeft[u] = i; return true; } } } return false; } int MaxMatch() { 
    //最大匹配，在主函数中直接调用MaxMatch()，返回最大匹配数。 int ans(0); memset(nextLeft,-1,sizeof(nextLeft)); memset(nextRight,-1,sizeof(nextRight)); for (int i = 1; i<=n; i++) { 
    if (-1 == nextLeft[i]) { 
    // { 
    memset(vis,0,sizeof(vis)); if (Find(i)) ans++; } } return ans; } int main(int argc,char *argv[]) { 
    scanf("%d%d%d", &n,&m,&e); for (int i = 1; i <= e; i++) { 
    int u,v; scanf("%d%d", &u,&v); if (u>=1&&u<=n&&v>=1&&v<=m) { 
    map[u][v] = 1; } } printf("%d\n", MaxMatch()); return 0; } 

$$Hopcroft-Karp算法$$
该算法也是求二分图最大匹配的，不过相对与匈牙利算法而言，效率更高，时间复杂度更优秀，但缺点是书写麻烦。

• Hopcroft-Karp 算法
  HK算法相比匈牙利算法高效的地方在于寻找增广路上，匈牙利算法是每次迭代的时候寻找一条增广路，而HK算法是先寻找一个增广路集合，在一次搜索中寻找多条不相交的增广路径，形成极大增广路径集。
  HK算法的复杂度 O($n^{\frac{1}{2}}\times m$)
  主函数直接调用MaxMatch().
  
  
  

//Hopcroft-Karp 算法 时间复杂度为O(n^(1/2)*m) //该算法是对匈牙利算法的优化,利用匈牙利算法一次只能找到一条增广路径， //Hopcroft-Karp就提出一次找到多条不相交的增广路径(不相交就是没有公共点和公共边的增广路径),称为增广路集 //然后根据这些增广路径添加多个匹配，并逐渐增加增广路径集中增广路径的长度。 #include "bits/stdc++.h" #define MAX 3003 #define INF 0x3f3f3f3f using namespace std; int nextLeft[MAX],nextRight[MAX]; //nextLeft[MAX]是左集合匹配右集合的点,同理nextRight也是 int dLeft[MAX],dRight[MAX]; //dLeft[MAX],dRight[MAX]是增广路径长度,或者说BFS深度 int dx[MAX],dy[MAX]; int map[MAX][MAX]; //map[MAX][MAX]存图 int nx,ny; //nx,ny分别是左集合点个数，右集合点个数 int dis; int vis[MAX]; //标记数组. bool searchPath() { 
    //寻找增广路径集,其增广路径集中每条增广路径长度一样 queue<int>Q; dis = INF; memset(dLeft,-1,sizeof(dLeft)); memset(dRight,-1,sizeof(dRight)); for (int i = 1;i <= nx; i++) { 
    //在BFS中宽度搜索 if (-1 == nextLeft[i]) { 
    //将未遍历的节点 入队 并初始化次节点距离为0  Q.push(i); dLeft[i] = 0; } } while (!Q.empty()) { 
    //广度搜索增广路径 int u = Q.front(); Q.pop(); if (dLeft[u] > dis) break; for (int v = 1; v <= ny; v++) { 
    //取右侧节点  if (map[u][v] && -1==dRight[v]) { 
    //右侧节点的增广路径的距离 dRight[v] = dLeft[u]+1; //v对应的距离 为u对应距离加1 if (-1 == nextRight[v]) dis = dRight[v]; else { 
    dLeft[nextRight[v]] = dRight[v]+1; Q.push(nextRight[v]); } } } } return dis != INF; } bool Find(int u) { 
    //Find函数，对增广路径集进行增广。 for (int v = 1; v <= ny; v++) { 
    if (!vis[v] && map[u][v] && dRight[v] == dLeft[u]+1) { 
    vis[v] = 1; if (nextRight[v] != -1 && dRight[v] == dis) continue; if (-1 == nextRight[v] || Find(nextRight[v])) { 
    nextRight[v] = u;nextLeft[u] = v; return true; } } } return false; } int MaxMatch() { 
    int ans(0); memset(nextRight,-1,sizeof(nextRight)); memset(nextLeft,-1,sizeof(nextLeft)); while(searchPath()) { 
    //不断进行增广路径集的操作，其增广路径也不断增长。 memset(vis,0,sizeof(vis)); for (int i = 1; i <= nx; i++) { 
    if (-1 == nextLeft[i]) { 
    if (Find(i)) ans++; } } } return ans; } int main(int argc,char *argv[]) { 
    // int n,m,e; int e; scanf("%d%d%d", &nx,&ny,&e); for (int i = 1; i <= e; i++) { 
    int u,v; scanf("%d%d", &u,&v); if (u>=1&&u<=nx&&v>=1&&v<=ny) { 
    map[u][v] = 1; } } printf("%d\n", MaxMatch()); return 0; } 

$$二分图多重匹配$$

• 多重匹配算法
  二分图普通的匹配是一对一的匹配，左集合X和右集合Y是一一对应的关系，如果允许Y集合中的一个元素和集合X中的多个元素匹配(通常有一个最大限制n)，但是X集合中的一个元素只能和Y集合的一个元素匹配，这就是二分图多重匹配的模型
  
• 算法步骤
  在构造二分图的多重匹配模型时，由于集合Y中的一个元素可以同时匹配集合X中的多个元素。所以，匈牙利算法中的cy[MAX]应该更换为一个二维数组 cy[MAX][MAX]。cy[i][j]，表示与元素$y_i$匹配的第j个元素，同时用vcy[i]来记录与元素$y_i$匹配的元素的数量。
  二分查找可以构成多重匹配的limit值。在主函数main()方法中进行二分查找，并调用MulMatch()就可以得到limit值。
  
  

/*二分图多重匹配算法*/ #include "bits/stdc++.h" #define MAX 1001 int bmap[MAX][MAX]; int vis[MAX]; int nx,ny; int vcy[MAX]; int cy[MAX][MAX]; int limit; int left;int right; bool Find(int u) { 
    for (int i = 1; i <= ny; i++) { 
    if (bmap[u][i] && !vis[i]) { 
    vis[u] = 1; if (vcy[i] < limit) { 
    cy[i][vcy[i]++] = u; return true; } for (int j = 1; j <= vcy[i]; j++) { 
    if (Find(cy[i][j])) { 
    cy[i][j] = u; return true; } } } } return false; } bool MulMatch() { 
    memset(vcy,0,sizeof(vcy)); for (int i = 1; i <= nx; i++) { 
    memset(vis,0,sizeof(vis)); if (!Find(i)) return false; } return true; } using namespace std; int main(int argc,char *argv[]) { 
    /* 根据题意建图... */ left = 0, right = nx; //二分查找 while (left < right) { 
    limit = (left+right)/2; if (MulMatch()) right = limit; else left = limit+1; } /* 根据题意输出... */ return 0; } 

$$二分图最佳匹配$$

• Kuhn－Munkres算法

/*二分图最佳匹配算法*/ /*Kuhn－Munkres算法*/ /*hdu 2255 例题*/ #include "bits/stdc++.h" #define MAX 1001 #define INF 0x3f3f3f3f using namespace std; int bmap[MAX][MAX]; int visx[MAX],visy[MAX],cx[MAX],cy[MAX]; int nextLeft[MAX],nextRight[MAX]; int w[MAX][MAX]; int n,m,ans; //n左m右 bool Find(int x) { 
    visx[x] = 1; for (int i = 1; i <= m; i++) { 
    if (!visy[i] && (cx[x]+cy[i] == w[x][i])) { 
    visy[i] = 1; if (!nextRight[i] || Find(nextRight[i])) { 
    nextRight[i] = x; nextLeft[x] = i; return true; } } } return false; } int kuhnMunkres() { 
    for (int i = 1; i <= n; i++) { 
    while (1) { 
    int D = INF; memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if (Find(i)) break; for (int j = 1; j <= n; j++) { 
    if (visx[j]) for (int k = 1; k <= m; k++) if (!visy[k]) D = min(D,cx[j]+cy[k]-w[j][k]); } if (D == INF) return -1; for (int j = 1; j <= n; j++) if (visx[j]) cx[j] -= D; for (int j = 1; j <= m; j++) if (visy[j]) cy[j] += D; } } ans = 0; for (int i = 1; i <= m; i++) ans += w[nextRight[i]][i]; return ans; } int main(int argc, char const *argv[]) { 
    while (scanf("%d", &n)!=EOF) { 
    m = n; memset(cy,0,sizeof(cy)); memset(cx,0,sizeof(cx)); memset(w,0,sizeof(w)); for (int i = 1; i <= n; i++) { 
    int D = 0; for (int j = 1; j <= m; j++) { 
    scanf("%d", &w[i][j]); D = max(D,w[i][j]); } cx[i] = D; } memset(nextLeft,0,sizeof(nextLeft)); memset(nextRight,0,sizeof(nextRight)); int ANS = kuhnMunkres(); printf("%d\n", ANS); } return 0; }