二分匹配

二分图

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

 

二分匹配

设G=，E>， M  E， 若M中任何两边不相邻，则称M是为G中的匹配，若在M中再加任意一条边后，所得集合都不是匹配了，则M是极大匹配，边数最多的匹配为最大匹配。

设e=（vi， vj）  M，则称vi，vj被M匹配。

对于任意的v V（G），若存在边e M，使e，v关联，则称v为M-饱和点，否则M-非饱和点。

若G中每个顶点都是M-饱和点，则称M为G中的完美匹配。

称G中在M和（E(G)-M）中交替取边的路径P为M的交错路径（增广路，交错轨），起点和终点都是M-非饱和点的交错路径称可增广轨。

 

匈牙利算法

（1）       置M为空

（2）       找出一条增广路径P，通过取反操作获得更大的匹配M’代替M（所谓取反操作就是本来属于M的边设成不属于M，不属于M的边设成属于M，这样匹配数就多了一个，如下图）

 

 

（3）       重复（2）操作，直到找不出增广路为止。

 

伪代码：

bool 寻找从k出发的对应项出的可增广路
{
    while (从邻接表中列举k能关联到顶点j)
    {
        if (j不在增广路上)
        {
            把j加入增广路;
            if (j是未盖点 或者 从j的对应项出发有可增广路)
            {
                修改j的对应项为k;
                则从k的对应项出有可增广路,返回true;
            }
        }
    }
    则从k的对应项出没有可增广路,返回false;
}
    
void 匈牙利hungary()
{
    for i->1 to n
    {
        if (则从i的对应项出有可增广路)
            匹配数++;
    }
    输出 匹配数;
}

来自某大牛博客：http://www.byvoid.com/blog/hungary/

里面还有详细图解

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define MAX 102

int n, n1, match;
int g[MAX][MAX];
int mat[MAX];
bool used[MAX];

bool find(int k)
{
       for(int i=1; i<=g[k][0]; i++) //从邻接表中列举k能关联到的顶点j

    {
        int j = g[k][i];
        if(!used[j]) //j不在增广路上

        {
            used[j] = true; //j加入增广路

            if(mat[j] == 0 || find(mat[j]))
                //j是未盖点 或者 从j的对应项出发有可增广路

            {
                mat[j] = k; //跟j对应项为k

                return true; //从k的对应项出有可增广路
            }
        }
    }
    return false;
}

void hungary()
{
    for(int i=1; i<=n1; i++)
    {
        if(find(i)) //从i的对应项出有可增广路
            match++; //匹配数++
        memset(used, 0, sizeof(used));
    }
}

int main()
{
    int i, j;
    int a, b;
    freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &n1);
    while(scanf("%d%d", &a, &b) != EOF)
    {
        g[a][++g[a][0]] = b; //建邻接表
    }
    match = 0;
    hungary();
    printf("%d\n", match);
    getch();
    return 0;
}