二分图匹配

序言：回忆起最初学习图匹配算法的艰辛与困惑，苦中有乐，但很多时间都浪费在了资料的寻找与甄别上。

因此，在对自己做一次知识总结的同时，整理与记录下了这些文字，希望能够给大家带来一定的帮助。

目录：第一部分：二分图的最大匹配第二部分：五种方式，两类构图第三部分：二分图匹配算法总结第四部分：二分图的最优权值匹配第五部分：一般图的最大匹配第六部分：图匹配题目列表符号说明：N,V：点数E：边数u,v,i,j：节点的标号INF：正无穷大-INF：负无穷大名词说明：时间复杂度：算法的理论时间上界时间效率：实际中算法运行的平均时间效率引用说明：文中参考了一些来源于网络的资料，也有原文全段引用的部分。

在这些资料被n+1次转载后，我已无法获知所有原作者的信息。

在此，对所有前辈们表示真诚的歉意和诚挚的敬意。

特别感谢Amber大神犀利的代码。

作者：Snow_storm正文：第一部分：二分图匹配有这么两个奇怪的工厂：工厂X只生产杯具，工厂Y只生产洗具。

最近，两个工厂决定将产品实行打包策略：即一个杯具搭配上一个洗具。

但由于杯具和洗具的形状和功能各不相同，对于某个类别的杯具来说，只能搭配某些类型的洗具。

现在，两个工厂的厂长大人想知道最多能成功的搭配多少对杯具与洗具。

类似于上面例子中提到的搭配问题，在图论中的有规范的名称：匹配。

注意到，上面的例子中涉及到的物品只有两类（杯具与洗具），且问题只涉及杯具与洗具的匹配，我们把这种只涉及一种关系的匹配问题称为二分匹配问题。

现在，让我们理清一些概念。

二分图：若图G中的点可以分为X和Y两部分，且每部分内部无任何边相连，则称图G为二分图。

匹配：无公共点的边集合（可以想象一下结婚这个词汇）。

匹配数：边集中边的个数最大匹配：匹配数最大的匹配。

如图1-1，展示的就是一个二分图：粗体线表示该二分图的一种匹配方式，不难发现，此时的匹配已经是最大匹配。

图 1-1如何能得到一个二分图的最大匹配？运用简单的枚举：找出全部匹配，然后保留匹配数最多的。

图论：⼆分图多重匹配使⽤最⼤流和费⽤流解决⼆分图的多重匹配之前编辑的忘存了好⽓啊。

本来打算学完⼆分图的乱七⼋糟的匹配之后再去接触⽹络流的，提前撞到了之前我们说的⼆分图最⼤匹配和⼆分图最⼤权匹配有⼀个特点，那就是没个点只能与⼀条边相匹配如果规定⼀个点要与L条边相匹配，这样的问题就是⼆分图的多重匹配问题然后根据边是否带权重，⼜可以分为⼆分图最⼤多重匹配和⼆分图最⼤权多重匹配（⼆分图多重最佳完美匹配）⾸先给出⼆分图多重最⼤匹配的做法：在原图上建⽴源点S和汇点T，S向每个X⽅点连⼀条容量为该X⽅点L值的边，每个Y⽅点向T连⼀条容量为该Y⽅点L值的边原来⼆分图中各边在新的⽹络中仍存在，容量为1（若该边可以使⽤多次则容量⼤于1），求该⽹络的最⼤流，就是该⼆分图多重最⼤匹配的值然后给出⼆分图多重最优匹配（⼆分图多重最⼤权匹配）的做法：在原图上建⽴源点S和汇点T，S向每个X⽅点连⼀条容量为该X⽅点L值、费⽤为0的边，每个Y⽅点向T连⼀条容量为该Y⽅点L值、费⽤为0的边原来⼆分图中各边在新的⽹络中仍存在，容量为1（若该边可以使⽤多次则容量⼤于1），费⽤为该边的权值。

求该⽹络的最⼤费⽤最⼤流，就是该⼆分图多重最优匹配的值这道题⾥⾯，⼀共有X⽅点这么多的电影，每个电影需要拍摄多少天就是对应的X⽅点L值，然后每⼀天是⼀个Y⽅点，由于每⼀天只能拍摄⼀部电影，所有Y⽅点的L值均为1下⾯介绍⼀下实现：int n,sum,cnt,ans;int g[maxn],cur[maxn];int str[25][10];struct Edge{int u,v,next,cap,flow;}e[maxm];这⾥⾯的cur数组是g数组的临时数组str⽤来保存每⼀个电影可以在哪⼀天拍摄Edge是⽹络流图⾥⾯的边void addedge(int u,int v,int c){e[++cnt].u=u;e[cnt].v=v;e[cnt].cap=c;e[cnt].flow=0;e[cnt].next=g[u];g[u]=cnt;e[++cnt].u=v;e[cnt].v=u;e[cnt].cap=0;e[cnt].flow=0;e[cnt].next=g[v];g[v]=cnt;}建图的时候，注意怎么赋值的接下来根据题意建图：for(int i=1;i<=n;i++){for(int j=1;j<=7;j++)scanf("%d",&str[i][j]);scanf("%d%d",&d,&w);sum+=d;addedge(0,i,d); //容量为需要多少天for(int j=1;j<=7;j++)for(int k=0;k<w;k++)if(str[i][j]) addedge(i,20+k*7+j,1);}for(int i=21;i<=370;i++) addedge(i,371,1);ans=maxflow(0,371);0为源点，371为汇点sum最后进⾏⼀个统计，和源点出发的最⼤流量进⾏⽐较，如果相等，说明电影排的开然后是求最⼤流的⼀个板⼦int maxflow(int st,int ed){int flowsum=0;while(bfs(st,ed)){memcpy(cur,g,sizeof(g));flowsum+=dfs(st,ed,INF);//cout<<"#"<<flowsum<<" ";}return flowsum;}具体的DFS和BFS这⾥不作为重点，以后再说下⾯给出完整的实现：1 #include<cstdio>2 #include<cstring>3 #include<algorithm>4using namespace std;5const int INF=1000000000;6const int maxn=1005;7const int maxm=20005;8int n,sum,cnt,ans;9int g[maxn],cur[maxn];10int str[25][10];11struct Edge{int u,v,next,cap,flow;}e[maxm];12void addedge(int u,int v,int c)13 {14 e[++cnt].u=u;e[cnt].v=v;e[cnt].cap=c;15 e[cnt].flow=0;e[cnt].next=g[u];g[u]=cnt;1617 e[++cnt].u=v;e[cnt].v=u;e[cnt].cap=0;18 e[cnt].flow=0;e[cnt].next=g[v];g[v]=cnt;19 }20int q[maxn],vis[maxn],d[maxn];21bool bfs(int st,int ed)22 {23 memset(q,0,sizeof(q));24 memset(vis,0,sizeof(vis));25 memset(d,-1,sizeof(d));26 vis[st]=1;d[st]=0;27int h=0,t=1;28 q[t]=st;29while(h!=t)30 {31 h=h%maxn+1;32int u=q[h];33for(int tmp=g[u];tmp;tmp=e[tmp].next)34 {35if(!vis[e[tmp].v]&&e[tmp].cap>e[tmp].flow)36 {37 vis[e[tmp].v]=1;38 d[e[tmp].v]=d[u]+1;39if(e[tmp].v==ed) return true;40 t=t%maxn+1;41 q[t]=e[tmp].v;42 }43 }44 }45return false;46 }47int getpair(int x)48 {49if(x%2==0)50return x-1;51else return x+1;52 }53int dfs(int x,int ed,int a)54 {55if(x==ed||a==0) return a;56int flow=0,f;57for(int tmp=cur[x];tmp;tmp=e[tmp].next)58 {59if(d[e[tmp].v]==d[x]+1&&(f=dfs(e[tmp].v,ed,min(a,e[tmp].cap-e[tmp].flow)))>0)60 {61 e[tmp].flow+=f;62 e[getpair(tmp)].flow-=f;63 a-=f;64 flow+=f;65if(a==0) break;66 }67 }68return flow;69 }70int maxflow(int st,int ed)71 {72int flowsum=0;73while(bfs(st,ed))74 {75 memcpy(cur,g,sizeof(g));76 flowsum+=dfs(st,ed,INF);77//cout<<"#"<<flowsum<<" ";78 }79return flowsum;8081 }82void init()83 {84 sum=cnt=0;85 memset(g,0,sizeof(g));86 }87int main()88 {89int T,d,w;90 scanf("%d",&T);91while(T--)92 {93 init();94 scanf("%d",&n);95for(int i=1;i<=n;i++)96 {97for(int j=1;j<=7;j++)98 scanf("%d",&str[i][j]);99 scanf("%d%d",&d,&w);100 sum+=d;101 addedge(0,i,d); //容量为需要多少天102for(int j=1;j<=7;j++)103for(int k=0;k<w;k++)104if(str[i][j]) addedge(i,20+k*7+j,1);105 }106for(int i=21;i<=370;i++) addedge(i,371,1);107 ans=maxflow(0,371);108if(ans==sum) printf("Yes\n");109else printf("No\n");110 }111return0;112 }据说这是典型的最⼤流题⽬，然⽽为了强⾏安利⼀波⼆分图的多重匹配，就不说成那个了。

设G=(V,{R})是一个无向图。

如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。

则称图G为二分图。

v给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

v选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)v如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。

但是这个算法的复杂度为边数的指数级函数。

因此，需要寻求一种更加高效的算法。

匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M 的一条增广路径。

由增广路径的定义可以推出下述三个结论：v 1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。

v 2. P经过取反操作（即非M中的边变为M中的边，原来M中的边去掉）可以得到一个更大的匹配M’。

v 3. M为G的最大匹配当且仅当不存在相对于M的增广路径。

从而可以得到求解最大匹配的匈牙利算法：v(1)置M为空v(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替Mv(3)重复(2)操作直到找不出增广路径为止根据该算法，我选用dfs (深度优先搜索)实现。

程序清单如下：int match[i] //存储集合m中的节点i在集合n中的匹配节点,初值为-1。

int n,m,match[100]; //二分图的两个集合分别含有n和m个元素。

bool visit[100],map[100][100]; //map存储邻接矩阵。

bool dfs(int k){int t;for(int i = 0; i < m; i++)if(map[k][i] && !visit[i]){visit[i] = true;t = match[i];match[i] = k; //路径取反操作。

二分图的最优匹配（KM算法）KM算法用来解决最大权匹配问题：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。

基本原理该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。

设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。

在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。

KM算法的正确性基于以下定理：若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。

首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。

这个定理是显然的。

因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。

所以相等子图的完备匹配一定是二分图的最大权匹配。

初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。

如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。

我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。

这时我们获得了一棵交错树，它的叶子结点全部是X顶点。

现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。

也就是说，它原来属于相等子图，现在仍属于相等子图。

2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。

匈牙利匹配算法的原理匈牙利匹配算法（也被称为二分图匹配算法或者Kuhn-Munkres算法）是用于解决二分图最大匹配问题的经典算法。

该算法由匈牙利数学家Dénes Kőnig于1931年提出，并由James Munkres在1957年进行改进。

该算法的时间复杂度为O(V^3)，其中V是图的顶点数。

匹配问题定义：给定一个二分图G=(X,Y,E)，X和Y分别代表两个不相交的顶点集合，E表示连接X和Y的边集合。

图中的匹配是指一个边的集合M，其中任意两条边没有公共的顶点。

匹配的相关概念：1.可增广路径：在一个匹配中找到一条没有被占用的边，通过这条边可以将匹配中的边个数增加一个，即将不在匹配中的边添加进去。

2. 增广路径：一个可增广路径是一个交替序列P=v0e1v1e2v2...ekvk，其中v0属于X且不在匹配中，v1v2...vk属于Y且在匹配中，e1e2...ek在原图中的边。

3.增广轨：一个交替序列形如V0E1V1E2...EkVk，其中V0属于X且不在匹配中，V1V2...Vk属于Y且在匹配中，E1E2...Ek在原图中的边。

增广轨是一条路径的特例，它是一条从X到Y的交替序列。

1.初始时，所有的边都不在匹配中。

2.在X中选择一个点v0，如果v0已经在匹配中，则找到与v0相连的在Y中的顶点v1、如果v1不在匹配中，则(v0,v1)是可增广路径的第一条边。

3. 如果v1在匹配中，则找到与v1相连的在X中的顶点v2，判断v2是否在匹配中。

依此类推，直到找到一个不在匹配中的点vn。

4.此时，如果n是奇数，则(n-1)条边在匹配中，这意味着我们找到了一条增广路径。

如果n是偶数，则(n-1)条边在匹配中，需要进行进一步的处理。

5.如果n是偶数，则将匹配中的边和非匹配中的边进行颠倒，得到一个新的匹配。

6.对于颠倒后的匹配，我们再次从第2步开始，继续寻找增广路径。

7.重复步骤2到步骤6，直到找不到可增广路径为止，此时我们得到了最大匹配。

[算法]⼆分图最⼤匹配前⾔具体什么是⼆分图，如何判定，可以参考。

定义简单来说，就是⼆分图中有满⾜任意两条边没有相同的点的边的集合，称为⼀组匹配，⽽边数最多的⼀组匹配称为该⼆分图的最⼤匹配。

在⼀组匹配中，属于这组边的称为匹配边，不属于的称为⾮匹配边，属于这组匹配的点称为匹配点，不属于的称为⾮匹配点。

匈⽛利算法⼜称增⼴路算法。

对于⼀组匹配 \(M\) ，若存在⼀条路径连接两个⾮匹配点，且使得匹配边与⾮匹配边交替出现，则称这条路径为增⼴路。

如上图，已匹配的边为红⾊，未匹配的边为绿⾊，则可以找到⼀组增⼴路 \(8\) ~ \(2\) ~ \(7\) ~ \(4\) 。

不难发现增⼴路具有以下特点：以⾮匹配边开始，在以⾮匹配边结尾，那么长度必为奇数。

路径上第⼀条边因为第⼀个点为奇数，则该路径上的第⼀个点为⾮匹配边，按照匹配边与⾮匹配边交替出现的性质可以得出，该路径的第奇数条边必为⾮匹配边，已经匹配的边必为第偶数条边，则有⾮匹配边的边数⽐匹配边的边数多⼀。

最⼤匹配中不会有增⼴路。

证明：假设最⼤匹配中存在增⼴路，则可以将增⼴路中的所有边的状态取反（即把⾮匹配边转换为匹配边，将匹配边转换为⾮匹配边），得到另⼀组匹配，⽽这组匹配的匹配边肯定会⽐之前的⼀组匹配的边数多⼀，则之前的这组匹配就不是最⼤匹配，与假设⽭盾，证毕。

在⼀张⼆分图中，若最⼤匹配为 \(S\) ，当且仅当 \(S\) 中不存在增⼴路。

其确性基于 \(hall\) 定理，⽐较复杂就不在详讲，主要讲找⼆分图最⼤匹配的⽅法。

⼤体思想就是枚举左部点，找到增⼴路后将这条路上的所有边的状态取反，得到边数更⼤的⼀组匹配。

在匹配过程中，有两种情况会改变当前左部点 \(u\) 的匹配情况。

1. 与之对应的右部点 \(v\) 是⾮匹配点，则可以将其的连边变为匹配边。

2. 与之对应的右部点 \(v\) 是匹配点，但与 \(v\) 已经匹配的点 \(u'\) 可以找到另⼀个未匹配的右部点 \(v'\) ，则 \(u\) ~ \(v\) ~ \(u'\) ~ \(v'\) 为⼀条增⼴路，则将其状态取反。