匈牙利算法

匈牙利算法适用于二分图匹配有关的问题

二分图（Bipartite graph）是一类特殊的图，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图。

img
img

可以看到，在上面的二分图中，每条边的端点都分别处于点集X和Y中。匈牙利算法主要用来解决两个问题：求二分图的最大匹配数和最小点覆盖数。

在图论中，一个“匹配”（matching）是一个边的集合，其中任意两条边都没有公共顶点。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路。

邻接矩阵算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n,m;//m代表右侧集合的元素数量,n代表左侧集合的元素数量
int map[MAXN][MAXN];//邻接矩阵存图
int match[MAXN];//记录当前右侧元素所对一个的左侧元素
bool vis[MAXN];//记录右侧元素是否被访问过

bool find(int x){
    for(int i = 1; i <= m; ++i){
        if(map[x][i] && !vis[i]) {//右边并且i没有被访问
            vis[i] = true;//记录状态为访问过
            if(match[i] == 0 || find(match[i])){//如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
                match[i] = x;//当前左侧元素成为当前右侧元素的新匹配
                return true;//返回匹配成功
            }
        }
    }
    return false;//循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian(){
    for(int i = 1; i <= n; ++i) {
        memset(vis, 0 , sizeof(vis));
        if(find(i)) ans ++;
    }
    return ans;
}

邻接链表算法

邻接链表数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Edge
{
    int to,next;
}edge[maxn];
//to 是该边指向的点 next表示源点为x的下一条边，这是遍历以x为源点的关键
int head[maxn],tot;//tot当前的边的数量;head[x]表示以x为源点的第一条边，初始值为-1
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}//初始化函数
void addedge(int u,int v)
{
    edge[tot].to=v;//对边进行编号
    edge[tot].next=head[u];//将U这个点上一次连接的点记录如果没有即为-1
    head[u]=tot++;//等于边的编号，之后edge[head[u]]即可调用这个边
}//加边函数

理解一下邻接链表：

邻接矩阵如下，但是它不适合稀疏图

邻接矩阵
邻接矩阵

邻接链表适合稀疏图：

邻接链表
邻接链表

因此结合上面的代码，head数组相当于邻接链表的一个个头，head[a]可以得到a的第一个边，通过edge[head[a]]获得，然后edge[head[a]].next可以得到下一条边的编号……

邻接链表匈牙利
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int maxn=200010;//边数的最大值
//参考资料https://zhuanlan.zhihu.com/p/96229700；
//整理的笔记:https://tyler-ytr.github.io/2021/04/13/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/
//邻接链表定义
struct Edge
{
    int to,next;
}edge[maxn];
//to 是该边指向的点 next表示源点为x的下一条边，这是遍历以x为源点的关键
int head[maxn],tot;//tot当前的边的数量;head[x]表示以x为源点的第一条边，初始值为-1
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}//初始化函数
void addedge(int u,int v)
{
    edge[tot].to=v;//对边进行编号
    edge[tot].next=head[u];//将U这个点上一次连接的点记录如果没有即为-1
    head[u]=tot++;//等于边的编号，之后edge[head[u]]即可调用这个边
}//加边函数
//匈牙利算法
int match[maxn];//记录当前右侧元素所对一个的左侧元素
bool vis[maxn];//记录当前右侧元素有没有被访问过
int N;//左侧元素的数量
bool dfs(int u){//dfs左侧元素
    for (int i=head[u];i!=-1;i=edge[i].next){//顺着边过去，一直遍历和这个点连接过的点和边;-1是邻接链表的最后
        int v=edge[i].to;
        if(!vis[v]){
            vis[v]=true;//记录状态为访问过
            if(match[v]==-1||dfs(match[v])){//如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
                match[v]=u;//当前左侧元素成为当前右侧元素的新匹配
                return true;//返回匹配成功
            }
        }
    }
    return false;
}

int Hungarian(){
    int res=0;
    memset(match,-1,sizeof(match));
    for(int i=0;i<N;++i){
        memset(vis,false,sizeof(vis));
        if(dfs(i))++res;
    }
    return res;
}

例题

问题 A: 二部图最大匹配

题目描述

输入一个由X、Y两部分组成的二部图，试求图上最大匹配的规模（无需输出方案）

输入

第1行输入两个数，分别代表X和Y部的顶点数 第2行~第x+1行，第i行的第一个数k表示X部第(i-1)个与Y部的k个点之间有边。接下来k个数为Y部与其有边的顶点的标号。（点的标号从1开始） 输入保证X部、Y部顶点数量均不超过10^5，总边数不超过2*10^5。

输出

输出1行，行内只有一个整数，为图上最大匹配的规模

样例输入
1
2
3
4
5
4 4
2 3 2
1 2
1 3
1 1
样例输出
1
3
提示：

样例解释：一个最大匹配是{(X1, Y3), (X2, Y2), (X4, Y1)} 。

一个显而易见的事实是：你不应该尝试使用邻接矩阵存储图上的边。

事实上，正确执行的算法并不需要每次遍历整个图（就像样例这样，除了X2以外的点搜索的第一条边就可以加入匹配）。我们提供的绝大部分数据是稀疏图，如果你的算法对此做了正确设计，使用C/C++实现的程序执行时间应该明显低于1秒。
如果你写出了时间复杂度Theta(V^2)的实现，那……也许你会在一部分数据上超时，也许不会

代码:(耗时99)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int maxn=200010;//边数的最大值
//参考资料https://zhuanlan.zhihu.com/p/96229700；
//整理的笔记:https://tyler-ytr.github.io/2021/04/13/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/
//邻接链表定义
struct Edge
{
    int to,next;
}edge[maxn];
//to 是该边指向的点 next表示源点为x的下一条边，这是遍历以x为源点的关键
int head[maxn],tot;//tot当前的边的数量;head[x]表示以x为源点的第一条边，初始值为-1
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}//初始化函数
void addedge(int u,int v)
{
    edge[tot].to=v;//对边进行编号
    edge[tot].next=head[u];//将U这个点上一次连接的点记录如果没有即为-1
    head[u]=tot++;//等于边的编号，之后edge[head[u]]即可调用这个边
}//加边函数
//匈牙利算法
int match[maxn];//记录当前右侧元素所对一个的左侧元素
bool vis[maxn];//记录当前右侧元素有没有被访问过
int N;//左侧元素的数量
bool dfs(int u){//dfs左侧元素
    for (int i=head[u];i!=-1;i=edge[i].next){//顺着边过去，一直遍历和这个点连接过的点和边;-1是邻接链表的最后
        int v=edge[i].to;
        if(!vis[v]){
            vis[v]=true;//记录状态为访问过
            if(match[v]==-1||dfs(match[v])){//如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
                match[v]=u;//当前左侧元素成为当前右侧元素的新匹配
                return true;//返回匹配成功
            }
        }
    }
    return false;
}

int Hungarian(){
    int res=0;
    memset(match,-1,sizeof(match));
    for(int i=0;i<N;++i){
        memset(vis,false,sizeof(vis));
        if(dfs(i))++res;
    }
    return res;
}

int main(){
//X为左侧，Y为右侧
    int M;
    cin>>N>>M;
    //printf("%d\n",N);
    int tempnum;
    int tempy;
    int j=0;
    init();
    for(int i=0;i<N;i++){
        //cin>>tempnum;
        scanf("%d",&tempnum);
        //printf("%d\n",tempnum);
        for (j=0;j<tempnum;j++){
            //cin>>tempy;
            scanf("%d",&tempy);
            addedge(i,tempy);
        }
    }
    //建图完毕
    int result = Hungarian();
    printf("%d\n",result);
    return 0;
}