HDUACM版13二分匹配及其应用

ACM12/14/20212今天，今天，你开始你开始 了吗？了吗？复习12/14/20213本周双星本周双星（1 12 2）：）：zhanlangzhanlang12/14/20214第十第十三三讲讲二分图及其应用二分图及其应用（Bipartite Graph）12/14/20215主要内容主要内容n什么是二分图什么是二分图n二分图的最大匹配二分图的最大匹配n匈牙利算法匈牙利算法n二分图的最小顶点覆盖二分图的最小顶点覆盖nDAGDAG图的最小路径覆盖图的最小路径覆盖n二分图的最大独立集二分图的最大独立集n处理技巧处理技巧12/14/20216什么是二分图？什么是二分图？n如果一个图的顶点可以分为两个集合如果一个图的顶点可以分为两个集合X X和和Y Y，图的所有边一定是有一个顶点属于集，图的所有边一定是有一个顶点属于集合合X X，另一个顶点属于集合，另一个顶点属于集合Y Y，则称该图，则称该图为为“二分图二分图”（ Bipartite Graph Bipartite Graph ）12/14/20217例例1 1：婚配问题：婚配问题男男女女12/14/20218二分图的最大匹配二分图的最大匹配在二分图的应用中，最常见的就是在二分图的应用中，最常见的就是最大匹配最大匹配问题，很多其他的问题都可以通过转化为匹问题，很多其他的问题都可以通过转化为匹配问题来解决。配问题来解决。12/14/20219如何求二分图的最大如何求二分图的最大匹配呢？匹配呢？12/14/202110经典算法：经典算法：匈牙利算法匈牙利算法12/14/202111匈牙利算法匈牙利算法( (求二分图最大匹配求二分图最大匹配) )n谈匈牙利算法自然避不开谈匈牙利算法自然避不开HallHall定理定理nHallHall定理：对于二分图定理：对于二分图G G，存在一个匹配，存在一个匹配M M，使得使得X X的所有顶点关于的所有顶点关于M M饱和的充要条件是：饱和的充要条件是：对于对于X X的任意一个子集的任意一个子集A A，和，和A A邻接的点集为邻接的点集为T(A)T(A)，恒有：，恒有： |T(A)| = |A| |T(A)| = |A| 12/14/202112图示（图示（1 1）：）：男1男2女1女2女3返回12/14/202113图示（图示（2 2）：）：男1男2女1女2女3返回X0=男2V1=男2V2 = T(V1)=女1Y=女1V1=男2，男1V2 =女1Y=女2MM E(P)( 其中，P是从x0 y的可增广道路 )12/14/202114匈牙利算法匈牙利算法基本步骤基本步骤：n1 1任给初始匹配任给初始匹配M M； n2 2若若X X已饱和已饱和则结束，则结束，否则否则进行第进行第3 3步；步； n3 3在在X X中找到一个非饱和顶点中找到一个非饱和顶点x0 x0， 作作V1 x0, V2 V1 x0, V2 ； n4 4若若T(V1) = V2T(V1) = V2则因为无法匹配而停止，否则因为无法匹配而停止，否则任选一点则任选一点y T(V1)V2y T(V1)V2； n5 5若若y y已饱和则转已饱和则转6 6，否则做一条从，否则做一条从x0 yx0 y的的可增广道路可增广道路P P，MMMM E(P)E(P)，转，转2 2； n6 6由于由于y y已饱和，所以已饱和，所以M M中有一条边中有一条边(y,z)(y,z)，作，作 V1 V1 z, V2 V2 yV1 V1 z, V2 V2 y， 转转4 4； 12/14/202115图示图示（3 3）：）：男男1男男2女女1女女2返回X0=X0=男男2 2V1=V1=男男22V2 = V2 = T(V1)=T(V1)=女女11T(V1) != V2T(V1) != V2Y=Y=女女1 1V1=V1=男男2 2，男，男11V2 =V2 =女女11T(V1)=V2T(V1)=V212/14/202116NOTE:真正求二分图的最大匹配真正求二分图的最大匹配的题目很少，往往做一些的题目很少，往往做一些简单的变化，比如简单的变化，比如12/14/202117变种变种1 1：二分图的最小顶点覆盖：二分图的最小顶点覆盖在二分图中求最少的点，让每条边都在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是至少和其中的一个点关联，这就是二分图的二分图的“最小顶点覆盖最小顶点覆盖”。12/14/202118实实 例例 分分 析析12/14/202119例例2 2：严禁早恋，违者开除！：严禁早恋，违者开除！男生男生女生女生12/14/202120例例3 3：HDOJ_1150 HDOJ_1150 任务安排任务安排有两台机器有两台机器A A和和B B以及以及N N个需要运行的任务。每个需要运行的任务。每台机器有台机器有M M种不同的模式，而每个任务都恰好种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器在一台机器上运行。如果它在机器A A上运行，上运行，则机器则机器A A需要设置为模式需要设置为模式ai,ai,如果它在机器如果它在机器B B上上运行，则机器运行，则机器A A需要设置为模式需要设置为模式bibi。每台机器。每台机器上的任务可以按照任意顺序执行，但是每台机上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。器重启次数尽量少。ACM/ICPC Beijing 2002ACM/ICPC Beijing 200212/14/202121图示：图示：结论：结论：二分图的最小二分图的最小顶点覆盖数顶点覆盖数 = =二分图的最大二分图的最大匹配数匹配数a0a1a2a3a4b0b1b2b3b412/14/202122特别说明特别说明: :n此题需要注意的一点，具体参见：此题需要注意的一点，具体参见： http:/ 2：DAGDAG图的最小路径覆盖图的最小路径覆盖用尽量少的不相交简单路径覆盖有向用尽量少的不相交简单路径覆盖有向无环图无环图(DAG)G(DAG)G的所有顶点，这就是的所有顶点，这就是DAGDAG图的最小路径覆盖问题。图的最小路径覆盖问题。12/14/202124例例4：HDOJ_1151 Air RaidHDOJ_1151 Air Raid有一个城镇，它的所有街道都是单有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。相连。同时已知街道不会形成回路。你的任务是编写程序求最小数量的你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（伞兵，这些伞兵可以访问（visitvisit）所）所有的路口。对于伞兵的起始降落点不有的路口。对于伞兵的起始降落点不做限制。做限制。12/14/202125Input:433 41 32 3Output: 2样本数据：样本数据：12/14/202126“空袭空袭”示意图示意图12344321132412/14/202127结论：结论：DAGDAG图的最小路径覆盖数图的最小路径覆盖数= =节点数（节点数（n n）- - 最大匹配数（最大匹配数（m m）关键：关键：求二分图的最大匹配数求二分图的最大匹配数12/14/202128变种变种3:3:二分图的最大独立集二分图的最大独立集HDOJ_1068 Girls and BoysHDOJ_1068 Girls and Boys 大学二年级的时候，一些同学开始研究大学二年级的时候，一些同学开始研究男女同学之间的缘分。研究者试图找出男女同学之间的缘分。研究者试图找出没有缘分同学的最大集。程序的结果就没有缘分同学的最大集。程序的结果就是要输出这个集合中学生的数量。是要输出这个集合中学生的数量。12/14/202129样本数据：样本数据：输入：输入：70: (3) 4 5 61: (2) 4 62: (0)3: (0)4: (2) 0 15: (1) 06: (2) 0 1输出：输出：5 5 12/14/20213000154326543216“Girls and Boys”示意图示意图12/14/202131结论：结论：二分图的最大独立集数二分图的最大独立集数= =节点数（节点数（n n） 最大匹配数（最大匹配数（m m）关键：关键：求二分图的最大匹配数求二分图的最大匹配数12/14/202132Any Questions?Any Questions?12/14/202133相关练习n201003201003ACMACM程序程序设计设计在在线线作作业业（1313） 二分匹配二分匹配12/14/202134附:参考源码(HDOJ-1150)/*hdoj_1150匈牙利算法 月下版 */#include#include#includeusing namespace std;bool mark1100,mark2100;int list100;int n,m,edge,num;vectorvector v;bool dfs(int to)register int i,point,s = listto;for(i=0;ivs.size();i+)point = vsi;if(!mark2point)continue;mark2point = false;if(listpoint=-1 | dfs(point)listpoint = s;return true;return false; void Solve()int i,j,point;bool flog = false;memset(mark1,true,sizeof(mark1);memset(list,-1,sizeof(list);num=0;for(i=0;in;i+)for(j=0;jvi.size();j+)if(listvij = -1)mark1i = false;listvij = i;num+;if(i=0) flog = true;break; for(i=0;in;i+)if(mark1i)if(!vi.empty()memset(mark2,true,sizeof(mark2);for(j=0;jvi.size();j+)point = vij;if(!mark2point) continue;mark2point = false;if(listpoint = -1 | dfs(point)listpoint = i;num+;break; mark1i = false; if(flog | list0 != -1)cout num-1 endl;else cout num n)if(n = 0)break;v.clear();v.resize(n);cin m edge;for(i=0;i j s d;vs.push_back(d); Solve(); return 0; 12/14/202135Welcome to HDOJWelcome to HDOJThank Thank You You