要么改变世界,要么适应世界

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

2020-11-27 13:24:12
115
目录

前言

二分图

G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点ij分别属于这两个不同的顶点集(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;
}
历史评论
开始评论