(HDUACM2010版_13)二分匹配及其应用PPT学习课件

ACM编程，杭州电子技术大学刘春英acm，1，2，2，2，今天开始？回顾，2，3，本周双星(12):zhanglang，第2，4，13节课，2分图及其应用(BipartiteGraph)，2，5，2，5，5，如果图形的顶点可以分为两个集合x和y，图形的所有边必须属于集合x，其他顶点属于集合y，则该图形为“平分图形”(BipartiteGraph)，2，7，示例1:婚姻问题，男人，女人，2，8，平分图形的最大匹配，2，9，二分图的最大匹配的求方法是什么？2，10，经典算法：匈牙利算法，2，11，匈牙利算法(二分图的最大匹配)，匈牙利算法无法说的自然Hall定理Hall定理：对于二分图g，对m饱和的x的所有顶点的要求是x的所有子集A和A的相邻点集为T(A) X0=南2V1=南2 v2= t (v1)=女1Y=女1V1=南2，南1V2=女1Y=女2m 59e 随机X饱和时终止，否则进行第三阶段。在1 x0 ，v2x中查找不饱和顶点x0。4.T(V1)=V2不可匹配地停止。否则，选择y-t(v1) v2。5.如果y饱和，则移至6，否则从x0y移至可扩展道路p，mme(p)，2。6.y饱和，因此m有v1-v1 z 、v2- y 、4的变异。2，15，图标(3):返回，X0=南2V1=南2 v2= t (v1)=女1T(V1)！=V2Y=女人1V1=男人2，男人1V2=女人1 t (v1)=v2，2，16，note 3360，很少有主题真正求二分法的最大匹配，经常是，2，2，18，案例分析，2，19，例子2:禁止早恋，开除违规者！男孩，女孩，2，20，示例3: hdoj _ 1150作业计划，两台机器a和b，以及n个需要执行的作业。每台计算机都有m种不同的模式，每个作业正好在一台计算机上运行。如果在系统a上运行，则必须将系统a设置为模式ai；如果在系统b上运行，则必须将系统a设置为模式bi。可以按任意顺序执行每个系统的操作，但是每个系统在每次转换模式时都必须重新启动。各作业合理安排设备，排序，尽量少重启设备。 ACM/icpc beijin 2002，2，21，图标：结论：2分钟的最小顶点复盖范围=2分钟的最大匹配数，2，22，特别是3360，对于此问题有一个注意事项。请参见：2，23，变体2:复盖DAG图中的最小路径，用不相交的可能简单路径复盖无回路(DAG)G中的所有顶点。这是Dag图的最小路径复盖问题。2，24，范例4: hdoj _ 1151 air raid，有一个城市，所有距离均为一行，并且每个距离连接至两个交叉。同时，距离不形成电路。你的任务是编写能够访问(visit)所有入口的最低数量伞兵的程序。对伞兵的初始降落点没有限制。2，25，input :4334323，output :2，样例数据：2，26，“空袭”图，2，27，结论：DAG图的最小路径复盖范围研究者们努力寻找没有缘分的同学最大的插曲。这个聚会的结果是计算这个中学生的人数。，2，29，样例数据：输入：70:(3)451:(2)4623360(0):(0)4:(2)0153:2，33，相关练习，201003 ACM程序设计在线工作(13)平分，参考源代码(HDOJ-1150)，/*hdoj_1150匈牙利算法月下旬*Boolmark1100、mark 2100；int list100；Intn、m、edge、numVectorvBool DFS (int to) register inti，point，s=listto；for(I=0)；Imedgef