匈牙利算法c语言代码

以下是匈牙利算法的C语言代码实现：

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

#define MAX 1001

int match[MAX]; // 存储匹配的结果
int vis[MAX]; // 标记是否被访问过
int g[MAX][MAX]; // 存储二分图的邻接矩阵
int n, m; // n表示左侧点的数量，m表示右侧点的数量

int dfs(int u) {
    for (int i = 1; i <= m; i++) {
        if (g[u][i] && !vis[i]) { // 如果存在一条边且右侧点未被访问
            vis[i] = 1; // 标记右侧点已被访问
            if (match[i] == -1 || dfs(match[i])) { // 如果右侧点未匹配或者右侧点已匹配但可以找到其他匹配
                match[i] = u; // 更新匹配结果
                return 1;
            }
        }
    }
    return 0;
}

int hungary() {
    int ans = 0;
    memset(match, -1, sizeof(match)); // 初始化匹配结果
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis)); // 初始化右侧点的访问状态
        if (dfs(i)) { // 如果可以找到一条增广路径
            ans++;
        }
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(g, 0, sizeof(g)); // 初始化邻接矩阵
    int u, v;
    while (scanf("%d%d", &u, &v) != EOF) {
        g[u][v] = 1; // 添加边
    }
    printf("%d\n", hungary()); // 输出最大匹配数
    return 0;
}