详解C++实现匈牙利算法

int M, N;            //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN];         //记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      //记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 //记录状态为访问过
            if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    //当前左侧元素成为当前右侧元素的新匹配
                return true; //返回匹配成功
            }
        }
    return false; //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}

#include <cstdio>
#include <cstring>
int Map[205][205], p[205], vis[205], N, T;
bool match(int i){
    for (int j = 1; j <= N; ++j){
        if (Map[i][j] && !vis[j]){
            vis[j] = 1;
            if (p[j] == 0 || match(p[j])){
                p[j] = i;
                return true;
            }
        }
    }
    return false;
}
int Hungarian(){
    int cnt = 0;
    for (int i = 1; i <= N; ++i){
        memset(vis, 0, sizeof(vis));
        if (match(i))
            cnt++;
    }
    return cnt;
}
int main(){
    scanf("%d", &T);
    while (T--){
        scanf("%d", &N);
        memset(p, 0, sizeof(p));
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                scanf("%d", &Map[i][j]);
        puts(Hungarian() == N ? "Yes" : "No");
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#define MAXN 5500
struct Edges
{
    int to, next;
} edges[MAXN * 8];
int Map[105][105], head[MAXN], p[MAXN], vis[MAXN], N, cnt_edge;
inline int add(int from, int to)
{
    edges[++cnt_edge].next = head[from];
    head[from] = cnt_edge;
    edges[cnt_edge].to = to;
}
inline int trans(int i, int j, int n) //把坐标转化为编号
{
    return ((i - 1) * n + j + 1) / 2;
}
bool match(int i)
{
    for (int e = head[i]; e; e = edges[e].next)
    {
        int j = edges[e].to;
        if (!vis[j])
        {
            vis[j] = true;
            if (p[j] == 0 || match(p[j]))
            {
                p[j] = i;
                return true;
            }
        }
    }
    return false;
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= N; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if (match(i))
            cnt++;
    }
    return cnt;
}
int main()
{
    int n, m, x, y;
    scanf("%d%d", &n, &m);
    N = (n * n + 1) / 2;
    memset(Map, -1, sizeof(Map));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            Map[i][j] = 0;
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d", &x, &y);
        Map[x][y] = -1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i % 2 ? 1 : 2; j <= n; j += 2)
            if (Map[i][j] == 0)
            {
                if (Map[i + 1][j] != -1)
                    add(trans(i, j, n), trans(i + 1, j, n));
                if (Map[i][j + 1] != -1)
                    add(trans(i, j, n), trans(i, j + 1, n));
                if (Map[i - 1][j] != -1)
                    add(trans(i, j, n), trans(i - 1, j, n));
                if (Map[i][j - 1] != -1)
                    add(trans(i, j, n), trans(i, j - 1, n));
            }
    printf("%d\n", Hungarian());
    return 0;
}