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

匈牙利算法原理

匈牙利算法的基本原理就是寻找增广路径，由于增广路径的重性质（非匹配边比匹配边多一条），只要交换增广路径里的匹配边和非匹配边，就可以使匹配边增加一条，改善匹配，通过不停的寻找增广路径，增加匹配边，当找不到增广路径时，匹配数自然就达到了最大。

如何不断寻找新的增广路径

我们可以从二分图的左点集中的点作为起点，逐个出发寻找匹配路径，在每次寻找增广路径时，并不会影响之前已经匹配的点的匹配性，（例如，在寻找2的匹配点时，会导致1的匹配点由a变为b，但不会导致1失配,寻找3的匹配点时，不会影响1和2的匹配点），所以当我们逐个寻找完以左点集中的点为顶点的增广路径时，左点集中的点已经达到了最多的匹配数，这也是二分图的最大匹配。

增广路径的性质补充

1－增广路径长度必定为奇数。
2－起点在左，终点在右。
3－路径中的点左右交替出现。
4－只有起点和终点是未覆盖点，其他点都配对。
5－对增广路径编号，所有奇数的边都不在M中，偶数边在M中。

为什么匈牙利算法中二分图左右点集中的点序号可以重复

这里主要是解释大家在看一些题解时，为什么左点集和右点集中的点都从1开始标号，要知道这样是会导致同一个图里点的标号重复的。
主要原因是在匈牙利算法中，我们对左右点集所需要的信息是并不相同的，我们需要左点集中的点都与右点集哪些点相连（虽然只需要知道左点集的这一信息，但其实图的信息是完整的），而对右顶点，我们则需要其“是否被访问过”这一信息，和在寻找增广路径的过程中与之匹配的点这一信息，左右点的信息分别存在不同的数据结构中，不相互影响，所以左右点集的点序号可以重复。

补充题目

来自网络流24题的变种

题目描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。 对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入格式

多组数据输入
第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数。
接下来m行，每行的第一个数输入K，K是与外籍飞行员可配对的英国飞行员编号，0<=K<=n;
之后K个数代表与外籍飞行员i匹配的英国飞行员编号。

输出格式

对每组数据输出一行，为皇家空军能派出的最多飞机数

输入样例

3 4
3 1 2 3
2  2 3
1 1
0

2 2
2 1 2
1 1

输出样例

3
2

代码

//dfs部分来自某模板，如有侵权，请联系我更改
#include <cstdio>
#include <cstring>
#include <vector>
#define MaxSize 10005
#define INF 0x3f3f3f3f
using namespace std;

int n,m, ans;
vector<int> G[MaxSize];//记录可攻击的敌方随从
int match[MaxSize];//记录匹配点
int visit[MaxSize];//记录是否访问

int A[MaxSize],B[MaxSize];

bool dfs(int x)//寻找增广路径
{
    for (int i = 0; i < G[x].size(); ++i)
    {
        int to = G[x][i];
        if(!visit[to])
        {
            visit[to] = 1;
            if(!match[to] || dfs(match[to]))
            {
                match[to] = x;
                return true;
            }
        }
    }
    return false;
}

int MaxMatch()
{
    ans = 0;
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= m; ++i)
    {
        memset(visit, 0, sizeof(visit));//清空访问
        if(dfs(i)) ans++;//从节点i尝试扩展
    }
    return ans;
}

int main()
{
    while(~scanf("%d%d", &n,&m))
    {
        int k,temp;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&k);
            for(int j=1;j<=k;j++)
            {
                scanf("%d",&temp);
                G[i].push_back(temp);
            }
        }
        printf("%d\n",MaxMatch());


    }
    return 0;
}