@[toc]

二分图:

二分图是一个无向图,点集分成子集X和Y,图中每一条边都是一边在X一边在Y
当且仅当无向图G的每一个回路次数都是偶数时(包括0),G就是一个二分图
在这里插入图片描述

匹配

介绍完二分图后我们看看匹配
匹配:如果任意两个边的端点都不相同,我们就称之为匹配。匹配是边的集合
最大匹配:所含匹配边数最多的匹配
完美匹配:在一次匹配中,所有的顶点都是匹配点
完美匹配一定是最大匹配,但是反过来不一定

匈牙利算法

以上讲的均为离散知识,现在开始讲算法
交替路:从一个未匹配点开始,按照非匹配边,匹配边,非匹配边。。。。这样的顺序形成的路径
增广路:从一个未匹配点开始,走交替路,如果途中经过另一个未匹配点,则这条交替路叫做增广路
增广路特点:非匹配边比匹配边多一条
算法核心就是寻找增广路径,直到没有
匈牙利算法寻找最大匹配,就是通过不断寻找原有匹配M的增广路径,因为找到一条M匹配的增广路径,就意味着一个更大的匹配M ' ,其恰好比M多一条边。这样不断更新,找不到就是最大情况
过程:
一开始随便选一个未匹配点,先是匹配(x1,y1),标记,然后给x2匹配,匹配(x2,y2),这样就形成匹配M,有两条边,目前没问题
然后x3匹配,发现y1已经被x1抢占了,然后x3横刀夺爱抢走y1,x1悲恨交加只能找下一个,然后把x2的对象y2也抢了,x2也只能顺位找y5,(这是个递归的过程,直到匹配到未被抢占的),这就形成匹配M1
刚才的争执过程(x3,y1,x1,y2,x2,y5),这就是匹配M的增广路
发现增广路就说明有更优的情况,所以我们由匹配M扩展到现在的M1
然后将x4加入,一次类推
如果争执过程中,最后一个人没找到对象怎么办?那也没事,反正整体的数量不会亏
在这里插入图片描述

代码:

我珍藏多年的模板

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 3;
int n = maxn, m = maxn;
int Map[maxn][maxn];//map[i][j]=1表示X部的i和Y部的j存在路径,是否可以匹配
int cx[maxn], cy[maxn];
bool vis[maxn];
//cx[i]表示X部i点匹配的Y部顶点的编号
//cy[i]表示Y部i点匹配的X部顶点的编号

bool dfs(int u)//dfs进入的都是X部的点
{
    for (int v = 0; v < n; v++)//枚举Y部的点,判断X部的u和Y部的v是否存在路径
    {
        //如果存在路径并且还没被标记加入增广路
        if (Map[u][v] && !vis[v])//vis数组只标记Y组
        {
            //标记加入增广路
            vis[v] = 1;

            //如果Y部的点v还未被匹配
            //或者已经被匹配了,但是可以从v点原来匹配的cy[v]找到一条增广路
            //说明这条路就可是一个正确的匹配
            //因为递归第一次进入dfs时,u是未匹配的
            //如果v还没有匹配对象,即和它相连的所有边都不在,已经选择的匹配边集合M(M\in E)中,这时就找到了u-v增广路径
            //如果v已经有匹配对象了,那么u-v是一条未选择的边,
            //而v-cy[v] \in M 则是一条已经选择的边, dfs(cy[v])从cy[v]开始搜索增广路径
                //如果新的v'没有匹配对象,那么u-v-cy[v]-v'就是一条增广路径,
                //如果v'已经有匹配对象了,那么根据匹配是唯一的,
                //cy[v]-v'一定不在已经选择的边中(和cy[v]-v冲突),
                //u-v-cy[v]-v'-cy[v']符合增广路径对边顺序的要求,继续利用dfs(cy[v'])搜索u-v-cy[v]-v'-cy[v']-下面的点
                //当搜索到增广链时,如u-v-cy[v]-v',那么经过递归的匹配调整和return 1,进行匹配增广操作,假设dfs0 是main调用的dfs算法,dfs1是dfs0调用的dfs算法
                //在dfs1中进行cy[v]-v'的匹配,因为dfs1返回1,因此在dfs0中进行u-v的匹配,匹配增广操作的结果是{cy[v]-v}->{u-v,cy[v]-v'}
                //如果在一个dfs(k)自调用的dfs(k+1)中,遍历所有的v(k+1),要么已经有匹配点了,要么和输入u(k+1)没有连接可能,这时搜索终止,说明不存在经过u(k+1)的增广链,返回0
                //而在main调用的dfs(0)中,调用的dfs(1)返回的都是0,而且v都是已经有匹配了,那么不存在从该点出发的增广链,那么就该点就不在最大匹配当中
                //为什么找不到增广链就不在最大匹配当中呢?感觉可以用反证法证明,博客中下面内容可能有更新这方面的思考
            if (cy[v] == -1 || dfs(cy[v]))
            {
                cx[u] = v;//可以匹配,进行匹配
                cy[v] = u;
                return 1;
            }
        }
    }
    return 0;//不能匹配
}
int maxmatch()//匈牙利算法主函数
{
    int ans = 0;
    //匹配清空,全部置为-1
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    for (int i = 0; i < n; i++)
    {
        if (cx[i] == -1)//如果X部的i还未匹配
        {
            memset(vis, 0, sizeof(vis));//每次找增广路的时候清空vis
            ans += dfs(i);
        }
    }
    return ans;
}

int main()
{
    //输入匹配的两个点集合的数量
    cin >> n >> m;
    //输入两个点集合成员间的匹配可能
    int x, y;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        Map[x][y] = 1;
    }
    //执行匈牙利算法,输出最大匹配
    cout << maxmatch() << endl;
    return 0; 
}