纯C++实现匈牙利算法

匈牙利算法是一种求解二分图最大匹配的经典算法，下面是纯C语言实现的代码：

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

#define MAX_N 1000
#define MAX_M 1000

int n, m;
int match[MAX_N]; // 记录右部点的匹配情况
int vis[MAX_N]; // 记录左部点是否被访问
int e[MAX_N][MAX_N]; // 存储图的邻接矩阵

// 寻找增广路
int dfs(int u) {
    for (int v = 1; v <= m; v++) {
        if (e[u][v] && !vis[v]) {
            vis[v] = 1;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    memset(match, -1, sizeof(match));
    int u, v;
    while (scanf("%d %d", &u, &v) != EOF) {
        e[u][v] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) {
            ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

其中，变量`n`和`m`分别表示二分图的左部点数和右部点数，数组`match`记录右部点的匹配情况，数组`vis`记录左部点是否被访问，数组`e`存储图的邻接矩阵。函数`dfs`用于寻找增广路，返回值为是否找到了增广路。主函数中，首先输入二分图的左部点数和右部点数，然后输入每条边的信息，存储到邻接矩阵中。最后调用`dfs`函数寻找增广路，直到无法找到为止，返回最大匹配数。