二分图

概念介绍:

二分图

二分图又称作二部图,又称作偶图,是图论中的一种特殊模型
顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。
设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i
in A,j in B),则称图G为一个二分图。

简单来说,就是顶点集 V 可分割为两个互不相交的子集,且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

当图中的顶点分为两个集合,使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连时,此时是一特殊的二分图,称为完全二分图。

充要条件是:图 G 中至少存在两个点,且图中所有回路的长度均为偶数。

匹配

在给定一个二分图 G,在 G 的一个子图 M 中,若 M 的边集中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配。
简单来说,匹配就是一个二分图中边的集合,其中任意两条边都没有公共顶点。
如图,红边就是一个匹配

最大匹配

给定二分图 G 中的所有匹配,所含匹配边数最多的匹配,称为这个图的最大匹配,选择最大匹配的问题即为图的最大匹配问题
如图,红边就是一个最大匹配

完全匹配

一个匹配中,图中每个顶点都与图中某条边相关联,则称此匹配为完全匹配,即一个图的某个匹配中,所有的顶点都是匹配点,就是一个完全匹配。

显然,由于完全匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突,因此完全匹配一定是最大匹配。但要注意的是,并非每个图都存在完全匹配。

简单来说,对于一个二分图,左点集中的每一个点都与右点集的一个点匹配,或者右点集中的每一个点都与左点集的一个点匹配。

完美匹配

对于一个二分图,左点集与右点集的点数相同,若存在一个匹配,包含左点集、右点集的所有顶点,则称为完美匹配。
简单来说,对于一个二分图,左点集中的每一个点都与右点集的一个点匹配,并且右点集中的每一个点都与左点集的一个点匹配。
如下图,红线所连接的匹配,不仅是一个完全匹配,还是一个完美匹配

最大匹配问题

举例来说,如下图所示,若存在某一对男孩和女孩之间存在相连的边,就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对,
使得每对儿都互相喜欢?这就是完全匹配问题。而最多有多少互相喜欢的男孩/女孩可以配对?这就是最大匹配问题。

最优匹配

带权二分图的权值最大的完全匹配称为最佳匹配,要注意的是,二分图的最优匹配不一定是二分图的最大权匹配。
实质上最优匹配问题就是求边权和最大的最大匹配问题。
求解技巧:可以添加一些权值为 0 的边,使得最优匹配和最大权匹配统一起来。

交替路

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

增广路

从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。
例如,图 5 中的一条增广路如图 6 所示(图中的匹配点均用红色标出):

增广路有一个重要特点:非匹配边比匹配边多一条。因此,研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。
由于中间的匹配节点不存在其他相连的匹配边,所以这样做不会破坏匹配的性质。交换后,图中的匹配边数目比原来多了 1 条。
其实,如果交替路以非匹配点结束的,那么这条交替路就是一条增广路
我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时,达到最大匹配(这是增广路定理)。匈牙利算法正是这么做的

1.匈牙利算法

基本思想:通过寻找增广路,把增广路中的匹配边和非匹配边的身份交换,这样就会多出一条匹配边,直到找不到增广路为止。

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
#include<bits/stdc++.h>
#define MAXN 9999
using namespace std;

int nx,ny;//nx表示二分图左边顶点的个数,ny表示二分图右边顶点的个数
int m;//m代表边的条数
int cx[MAXN],cy[MAXN];//如果有cx[i]=j,则必有cy[j]=i,说明i点和j点能够匹配
int x,y;//x点到y点有边
int e[MAXN][MAXN];//邻接矩阵
int visited[MAXN];//标记数组,标记的永远是二分图右边的顶点
int ret;//最后结果

int point(int u)//这个函数的作用是寻找增广路和更新cx,xy数组,如果找到了增广路,函数返回1,找不到,函数返回0。
{
for(int v=1;v<=ny;v++)//依次遍历右边的所有顶点
{
if(e[u][v]&&!visited[v])//条件一:左边的u顶点和右边的v顶点有连通边,条件二:右边的v顶点在没有被访问过,这两个条件必须同时满足
{
visited[v]=1;//将v顶点标记为访问过的
if(cy[v]==-1||point(cy[v]))//条件一:右边的v顶点没有左边对应的匹配的点,条件二:以v顶点在左边的匹配点为起点能够找到一条增广路(如果能够到达条件二,说明v顶点在左边一定有对应的匹配点)。
{
cx[u]=v;//更新cx,cy数组
cy[v]=u;

return 1;
}
}
}
return 0;//如果程序到达了这里,说明对右边所有的顶点都访问完了,没有满足条件的。
}

int main()
{
while (cin>>m>>nx>>ny)
{
memset(cx,-1,sizeof(cx));//初始化cx,cy数组的值为-1
memset(cy,-1,sizeof(cy));
memset(e,0,sizeof(e));//初始化邻接矩阵

ret=0;
while (m--)//输入边的信息和更新邻接矩阵
{
cin>>x>>y;
e[x][y]=1;
}
for(int i=1;i<=nx;i++)//对二分图左边的所有顶点进行遍历
{
if(cx[i]==-1)//如果左边的i顶点还没有匹配的点,就对i顶点进行匹配
{
memset(visited,0,sizeof(visited));//每次进行point时,都要对visited数组进行初始化

ret+=point(i);//point函数传入的参数永远是二分图左边的点
}
}
cout<<ret<<endl;
}
}

2.KM算法

KM算法写的比较好的文章
https://www.cnblogs.com/wenruo/p/5264235.html
https://www.cnblogs.com/logosG/p/logos.html?tdsourcetag=s_pcqq_aiomsg

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#include<algorithm>
#include<iostream>
#include<limits.h>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#define INT 9654234
#define mod 1000000007
typedef long long ll;
using namespace std;
const int MAXN = 305;

int N;
int ex_gir[MAXN];//每个妹子的期望值
int ex_boy[MAXN];//每个男生的期望值
bool vis_gir[MAXN];//记录每一轮匹配过的女生
bool vis_boy[MAXN];//记录每一轮匹配过的男生 每进行新的一轮,都要重新初始化这两个数组
int match[MAXN];//match[i]代表和i男生匹配的女生的编号
int slack[MAXN];//slack[i]代表i男生如果要获得女生的芳心,至少需要增加的期待值
int love[MAXN][MAXN];//记录每个妹子和男生的好感度

bool dfs(int gir)//dfs函数求的是编号为gir的女孩能否匹配到男生,如果能,返回true,否则,返回false
{
vis_gir[gir]=true;//标记
for(int i=1;i<=N;i++)
{
if(vis_boy[i])//我们规定每次匹配对于某个男生只访问一遍,如果先前访问过了,就换个男生
continue ;
int gap=ex_gir[gir]+ex_boy[i]-love[gir][i];

if(gap==0)//如果这个条件满足,说明编号为gir女孩和编号为i的男孩可能能够匹配成功
{
vis_boy[i]=true;//标记
if(match[i]==-1||dfs(match[i]))//如果这两个条件满足其中一个,说明编号为gir女孩和编号为i的男孩匹配成功
{
match[i]=gir;
return true;
}
}
else
slack[i]=min(slack[i],gap);//如果gap不等于0,说明当前状态编号为gir女孩和编号为i的男孩不可能匹配成功,更新slack[i]。
}
return false;
}

int km()
{
memset(match,-1,sizeof(match));
memset(ex_boy,0,sizeof(ex_boy));

for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
ex_gir[i]=max(love[i][j],ex_gir[i]);//初始化ex_gir数组
for(int i=1;i<=N;i++)
{
fill(slack,slack+N+1,INT);
while (1)//这个while循环结束的条件是直到让编号为i的女生找到可以匹配的男生后
{
memset(vis_gir,false,sizeof(vis_gir));
memset(vis_boy,false,sizeof(vis_gir));

if(dfs(i))//如果这个条件满足,说明编号为i的女生找到了匹配的男生,换下一个女生,如果这个条件不满足,说明这个女生没有匹配到男生,让这个女生降低期望值后继续匹配
break ;

int t=INT;

for(int j=1;j<=N;j++)//寻找在这一轮匹配中没有匹配到的男生如果要获得女生芳心所需要增加的期待值的最小值
if(!vis_boy[j])
t=min(t,slack[j]);

for(int i=1;i<=N;i++)//让在这一轮匹配中匹配过的女生的期待值减小,匹配过的男生的期待值增加
{
if(vis_gir[i])
ex_gir[i]-=t;

if(vis_boy[i])
ex_boy[i]+=t;
else
slack[i]-=t;//因为有些女生的期待值减小了,所以这一轮没有被匹配过的男生得到女生的芳心所需要增加的期待值就变小了,所以slack数组中的相应的值要变小
}
}
}
int res=0;//计算好感和
for(int i=1;i<=N;i++)
res+=love[match[i]][i];

return res;
}

int main()
{
cin>>N;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
cin>>love[i][j];

cout<<km()<<endl;
}

---------------- The End ----------------
0%