匈牙利算法求解二分图的最大匹配

前言

二分图：

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

匹配：

给定一个二分图G，在G的一个子图M中， M的边集{E}中的任意两条边都不交汇于同一个结点，则称M是一个匹配。

最大匹配：

给定二分图G的所有子图中，满足匹配条件的最大边数子图

关于更多的算法解析，请移步至这位作者的博客

算法实现

题目背景

HDU2063过山车

题解

#include <cstdio>
#include <cstring>
#include <iostream>
#define MAX_NUM 501
using namespace std;
bool graph[MAX_NUM][MAX_NUM];
bool visited[MAX_NUM];
// 存放每个男生匹配的女生
int matched[MAX_NUM];
int girlNum, boyNum;
int matching(int girl) {
    for (int boy = 1; boy <= boyNum; boy++) {
        if (graph[girl][boy] && !visited[boy]) {
            visited[boy] = true;
          	// 假若该男生未被匹配 或者 该男生匹配的女生 能够可以更换其他男生
            if (matched[boy] == 0 || matching(matched[boy]) == 1) {
                matched[boy] = girl;
                return 1;
            }
        }
    }
    return 0;
}
int Hungary() {
    int sum = 0;
    for (int girl = 1; girl <= girlNum; girl++) {
        memset(visited, false, sizeof(visited));
        sum += matching(girl);
    }
    return sum;
}
int main() {
    int k, girl, boy;
    while (~(scanf("%d", &k)) && k) {
        scanf("%d%d", &girlNum, &boyNum);
        memset(graph, false, sizeof(graph));
        memset(matched, 0, sizeof(matched));
        for (int i = 0; i < k; i++) {
            scanf("%d%d", &girl, &boy);
            graph[girl][boy] = true;
        }
        printf("%d\n", Hungary());
    }
    return 0;
}