(lecture092)二分图及其应用课件.ppt

1、1/6/20231ACM ACM 程序设计程序设计信息学院计算机应用系信息学院计算机应用系 余腊生余腊生1/6/20232请个假请个假,下周调课下周调课(西安西安)1/6/20233050721201/6/20234二分图及其应用二分图及其应用（Bipartite Graph&Applications）1/6/20235l什么是二分图l二分图的最大匹配l匈牙利算法l二分图的最小顶点覆盖lDAG图的最小路径覆盖l二分图的最大独立集l处理技巧1/6/20236l如果一个图的顶点可以分为两个集合X和Y，图的所有边一定是有一个顶点属于集合X，另一个顶点属于集合Y，则称该图为“二分图”（Bipartit

2、e Graph）1/6/20237男男女1/6/20238 在二分图的应用中，最常见的就是在二分图的应用中，最常见的就是最大匹配问题，很多其他的问题都最大匹配问题，很多其他的问题都可以通过转化为匹配问题来解决。可以通过转化为匹配问题来解决。1/6/202391/6/202310匈牙利算法匈牙利算法1/6/202311/*hdoj_1150匈牙利算法 月下版*/#include#include#includeusing namespace std;bool mark1100,mark2100;int list100;int n,m,edge,num;vectorvector v;bool dfs

3、(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(

4、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|list

5、0!=-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;1/6/202312l谈匈牙利算法自然避不开Hall定理lHall定理：对于二分图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有：|T(A)|=|A|1/6/202313男1男2女1女2女3返回1/6/202314男1男2女1女2女3返回X0=男2V1=男2V2=T

6、(V1)=女1Y=女1V1=男2，男1V2=女1Y=女2MM E(P)(其中，P是从x0 y的可增广道路)1/6/202315l1任给初始匹配M；l2若X已饱和则结束，否则进行第3步；l3在X中找到一个非饱和顶点x0，作V1 x0,V2 ；l4若T(V1)=V2则因为无法匹配而停止，否则任选一点y T(V1)V2；l5若y已饱和则转6，否则做一条从x0 y的可增广道路P，MM E(P)，转2；l6由于y已饱和，所以M中有一条边(y,z)，作 V1 V1 z,V2 V2 y，转4；1/6/202316男1男2女1女2返回X0=男2V1=男2V2=T(V1)=女1T(V1)!=V2Y=女1V1=男

7、2，男1V2=女1T(V1)=V21/6/202317真正求二分图的最大匹配的题目很少，往往做一些简单的变化，比如1/6/202318在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是“二分图的最最小小顶点顶点覆覆盖盖”。1/6/2023191/6/202320男生女生1/6/202321有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式ai,如果它在机器B上运行，则机器A需要设置为模式bi。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排

8、一台机器并合理安排顺序，使得机器重启次数尽量少。hdoj_1150（LRJ_p331）ACM/ICPC Beijing 20021/6/202322结论：结论：二分图的最小顶点覆盖数二分图的最小顶点覆盖数=二分图的最大匹配数二分图的最大匹配数a0a1a2a3a4b0b1b2b3b41/6/202323l此题需要注意的一点，具体参见：http:/ 有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（visit）所有的路口。对于伞兵的起始降落点不做限制。hdoj_1151 1/6/202326433 4

9、1 32 3Output:21/6/2023271234432113241/6/202328DAG图的最小路径覆盖数=节点数（n）-最大匹配数（m）关键：求二分图的最大匹配数1/6/202329Girls and Boys 大学二年级的时候，一些同学开始研究男女同学之间的缘分。研究者试图找出没有缘分同学的最大集。程序的结果就是要输出这个集合中学生的数量。hdoj_1068 1/6/202330 70:(3)4 5 61:(2)4 62:(0)3:(0)4:(2)0 15:(1)06:(2)0 1输出：输出：5 1/6/202331001543265432161/6/202332二分图的最大独立集数=节点数（n）最大匹配数（m）关键：求二分图的最大匹配数1/6/2023331/6/202334l1068 (二分图最大独立集=n-m)l1150 (二分图最小顶点覆盖=m )l1151 (二分图最小路径覆盖=n-m)1/6/202335下周调课下周调课(西安西安)1/6/2023361/6/202337ACM,天天见！天天见！