二分图-匈牙利算法

时间：2010-08-05 来源：Z_Q_2010

设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集V1、V2，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。二分图也可以记为G={V1,V2,E}。

给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。


增广路的定义(也称增广轨或交错轨)：
　　若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
　　由增广路的定义可以推出下述4个结论：
        1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
        2－P上所有第奇数条边都不在M中，所有第偶数条边都出现在M中。
　　    3－P经过取反操作可以得到一个更大的匹配M’。所谓“取反”即把P上所有第奇数条边(原不在M中)加入到M中，并把P中所有第偶数条边(原在M中)从M中删除，则新的匹配数就比原匹配数多了1个。（增广路顾名思义就是使匹配数增多的路径）
        4－M为G的最大匹配当且仅当不存在相对于M的增广路径。

用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)

　　(1)置M为空；
　　(2)找出一条增广路径P，通过取反操作获得更大的匹配M’（(M-P)∪(P-M)）代替M；
　　(3)重复(2)操作直到找不出增广路径为止。

#include <stdio.h>
#include <string.h>

const int Maxn=5;
int n1, n2, m, ans;
int link[Maxn];            //值为与V2中的相匹配的v1

bool visit [Maxn];        //记录V2中的每个点的访问

bool g[Maxn][Maxn];        //邻接矩阵，true代表有边v1->v2



void init()
{
    int t1, t2;
    memset(g, 0, sizeof(g));
    memset(link, 0, sizeof(link));

    scanf("%d%d%d", &n1, &n2, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &t1, &t2);
        g[t1][t2] = true;
    }
    return;
}

bool find(int v1)
{
    for(int v2=1;v2<=n2;v2++)
    {
        if(g[v1][v2]&&!visit[v2])    //visit[v2]使得找到由v1发出的新边

        {
            visit[v2] = true;

            if (link[v2] == 0|| find(link[v2]))
            {
                link[v2] = v1;        //存在一条增广路，更新匹配M（"取反"）

                return true;
            }
            //在最终递归为true的前提下(标明存在一条增广路)，首先递归的find(link[v2])=true为增广路的第一条边

            //其余的为增广路的中间边，最后的递归判断link[v2]=0为增广路的最后一条边

        }
    }
    return false;        //最终不能构成增广路

}

int main()
{
    init();

    ans=0;
    for (int v1 = 1; v1 <= n1; v1++)
    {
        memset(visit, 0, sizeof(visit));
        if (find(v1)) ans++;        //逐渐增大匹配数

    }
    printf("%d\n", ans);
    return 0;
}
//4 4 6

//1 1

//2 2

//2 4

//3 2

//3 3