毕业设计论文基于匹配算法的补考排考系统.doc

《毕业设计论文基于匹配算法的补考排考系统.doc》由会员分享，可在线阅读，更多相关《毕业设计论文基于匹配算法的补考排考系统.doc（45页珍藏版）》请在三一办公上搜索。

1、哈尔滨商业大学毕业设计（论文）基于匹配算法的补考排考系统学 生 姓 名 指 导 教 师 专 业 信息管理与信息系统 学 院 计算机与信息工程学院 2011年 5 月 14 日Graduation Project (Thesis)Harbin University of Commerce Examination Arrangement System Based Matching AlgorithmsStudent HUANG LIN Supervisor SUN JIAN MING Specialty Information Management and Information System S

2、chool Harbin University of Commerce 2011-05-15 Information Management and Information System 毕业设计（论文）任务书姓名：黄林学院：计算机与信息工程学院班级：07级2班专业：信息管理与信息系统毕业设计（论文）题目：多功能排考系统立题目的和意义：目 的： 能随时增加学生挂科信息，采用算法排出一个比较好的排考次序。能满足考次必要少，任何一个学生不会同时考多于一个科目。能显示每次考试的人数。意 义： 大学学生经常挂科，那么学校安排补考就是一项很重要的任务。安排的考次越少，越能节约老师和学生的时间。同时考试科目

3、不能和学生发生冲突（任何一个学生都不能同时考多于一门）。排考的效率关系到学校教务的水平和效率，一个好的排考算法很重要。技术要求与工作计划：技术要求：采用C/S结构。界面由VC开放出来，数据库采用MYSQL数据库。采用简单的两层结构。界面有MFC的单文档框架，减去了好多界面开放的步骤，并且界面简洁漂亮。工作计划：毕业论文设计大概分三个阶段来完成。（1）准备阶段：指导老师根据专业特点和培养要求布置毕业论文的选题工作，并利用假期时间查找相关资料，认真做好毕业设计的准备工作。（2）进行社会实践与调查，实现系统设计，撰写毕业论文阶段：完成实习报告的填写工作，并对系统进行总体分析和总体设计，按照软件开发的

4、结构化方法，对系统进行详细设计，并实现系统的编程设计，不断对系统进行调试与测试，实现各模块的功能，并开始撰写毕业论文，按规定时间向老师汇报论文写作情况并接受老师指导，按老师要求对论文进行修改，完成定稿。（3）上交毕业设计，并进行论文答辩阶段：按规定时间递交毕业论文，经初步审核后，进行论文答辩，由答辩委员会给定成绩，并撰写论文评语。时间安排：完成期限：2个月预期进度：2011年起始时间 结束时间 计划进度3月25日 4月 8日 文献检索，编写开题报告4月 9日 4月30日 外文资料翻译，系统设计、编码5月 1日 5月31日 系统设计、编码，测试6月 1日 6月 6日 撰写毕业设计报告6月7日 6

5、月 8日 上交毕业设计所有文档资料(含系统、毕业设计报告等)指导教师要求：（签字） 年 月 日教研室主任意见：（签字） 年 月 日院长意见：（签字） 年 月 日毕业设计（论文）审阅评语一、指导教师评语：指导教师签字：年 月 日毕业设计（论文）审阅评语二、评阅人评语：评阅人签字：年 月 日毕业设计（论文）答辩评语三、答辩委员会评语：四、毕业设计（论文）成绩：专业答辩组负责人签字：年 月 日五、答辩委员会主任签章答辩委员会主任单位： （签章） 答辩委员会主任职称： 答辩委员会主任签字： 年 月 日哈尔滨商业大学毕业设计（论文）摘要高校教务管理体系中，考试安排是日常工作的一项主要安排。随着高校规模扩

6、大了，在校学生增加了，排考工作日趋复杂，利用传统的人工方式进行排考急费时有费力，既吧科学又不能满足现在的要求。传统的人工方法是通过大量的人工计算，匹配，探测的数学方法排出一种考序，这种方法既要耗费大量的时间，一般要好长一段时间，但人数考试科目太多时候往往人工计算不出排考顺序，而将考试安排分配到个个专业，从而出现专业同一门课程多次考试的现象。出于这种现象利于计算机排考，成为必然要求。也是据以这种原因，本人设计出一套排靠系统，他能较好的解决了以往排考费时费力的问题。同时简化了操作过程，提高教学管理效率。本系统能同时具有输入学生考试科目和排考两种功能，既简洁又快速。排考问题面临的两个硬要求 1.同一

7、个学生不能同时考多于一个科目。2.人数多的科目应该先考，方便老师批改试卷。同时满足一个软要求，即每个考次的人数不会相差太多。本系统利用VC和MYSQL两大软件，采用的是C/S结构，客户端利用的是VC设计的界面，VC设计的界面既简洁有能快速完成界面设计，对于这种以计算为主的系统是首要选择。服务器，这里就是数据库了，是MYSQL，MYSQL数据库是一直开源的数据库，是一直中型的数据库软件，还是一套免费的数据库软件，所以对于我们这个排考系统，也是一直最好的选择。 关键词：排考系统，排考算法，匹配算法，VC+MYSQL，C/S。IIAbstractExam ination arrangement pl

8、ays avery important role of university educational administaation system.With the expansion of the university scale the number of student is increasing Exam arrangement has become more and more complicated. test, using the traditional manual way of scheduling urgent examination have demanding time-c

9、onsuming, adn not scientific and not meet current requirements. Traditional manual method is through the manual calculation, matching, Mathematical Methods of detecting discharge of a test sequence, This method not only want to spend a lot of time, generally better for a long time, but the number of

10、 examination subjects are often manual calculation is not too often a row of test order, and will be distributed to all professional examination arrangements, which appear professional examination of the same phenomenon repeated course. For this Phenomenon is conducive to the computer exam schedule,

11、 has become an inevitable requirement. Yeshi, according to this reason, I design a row by the system, he can more good solution to the previous problem of scheduling time-consuming test. While simplifying the operation process, to improve teaching management efficiency. The system can also have both

12、 input of students and discharge test test subjects two functions, both simple and fast. Scheduling problem faced by two hard test requirements 1. The same school Students can not test more than one subject. 2. The number of number of subjects should Xiankao to facilitate the teachers mark papers. T

13、o meet a soft Demand, the number of times that each test does not differ too much. The system uses two VC and MYSQL software, using C / S structure, Using the VC client interface design, VC interface design are both simple to quickly complete the interface design, to account for this, Operator-based

14、 system is the first choice. Server, this is the database is MYSQL, MYSQL database is always open .Key Words：examination arrangement system,automatic arrangement matching algorithms.VC +MYSQL,C/S struct.目 录摘要IAbstractII1绪 论51.1现代管理信息系统的概念51.2课题需求提出的目的及研发的切实意义61.2.1课题需求提出的目的61.2.2研发的切实意义62系统分析62.1需求分

15、析62.2可行性分析72.2.1经济可行性72.2.2技术可行性72.2.3管理可行性72.3 系统的软硬件介绍82.3.1系统的运行环境。82.3.2 开放技术82.3.3 MYSQL介绍。82.3.4 Microsoft Visual C+ 6.0简介92.4 系统使用开放技术介绍102.4.1 MFC 介绍102.4.2 C/S介绍112.5系统功能流程图123匹配算法介绍133.1 匹配算法介绍133.2 KM匹配算法的C语言实现介绍153.3 KMP匹配算法介绍164.本系统匹配算法实现174.1 系统算法说明174.2 算法流程图。194.3 系统算法实现的关键代码。204.3.1

16、 添加学生补考科目代码。204.3.2 程序功能说明204.3.3 程序执行功能示意图。214.3.4 科目匹配算法代码。214.3.5 排考程序说明。224.3.6 程序功能说明图。234.4 算法评价。245.系统功能实现255.1系统功能结构设计。255.1.1 输入学生补考信息模块255.1.2 排考功能模块255.2 数据库设计。265.3逻辑结构设计265.4插入学生补考信息实现功能。275.5 按匹配算法排考的功能实现。285.6 增大学生补考数据量进行排考。306 系统测试与维护326.1 系统测试326.1.1 系统测试的意义326.1.2 系统测试的方法326.2系统维护3

17、3结 论34参考文献35致 谢36哈尔滨商业大学毕业设计（论文）1 绪 论随着现代科学技术的迅猛发展，计算机技术已经渗透到各个领域，成为各行业必不可以少的工具。引入智能排考系统，利用人工把学生挂科信息输入到数据库中，使计算机采用程序员编写好的算法，计算出考次少，考试科目和学生又不冲突的考试安排。自动排考系统的应用必将推动教务系统信息化的进程。 1.1 现代管理信息系统的概念20世纪60年代，美国经营管理协会及其事业部第一次提出了建立管理信息系统的设想，即建立一个有效的信息系统，使得各级管理部门都能了解本单位一切有关的经营活动，为各级决策人员提供所需要的信息。但由于当时硬、软件技术水平的限制和开

18、发方法的落后，效果并不明显。进入20世纪80年代以后，随着各种技术特别是信息技术的迅速发展，管理信息系统也得到了进一步的发展，MIS的概念逐步得到了充实和完善。不同时期的研究者们从各自不同的角度对管理信息系统进行研究，从计算机系统实现、支持决策和人机系统的角度出发。分别给出了不同的定义，其中最具代表性的定义有以下几种：（1）管理信息系统是一个由人、计算机等组成的能进行管理信息手机、传递、储存、加工、维护和使用的系统。管理信息系统能实测企业的各种运行情况，利用过去的数据预测未来，从全局出发辅助企业进行决策，利用信息控制企业的行为，帮助企业实现其规划目标。（2）信息系统不仅是一个能向管理者提供帮助

19、的基于计算机的人机系统，而且也是一个社会技术系统，因此应将信息系统放在组织与社会的这个大背景中去考察，并把考察的重点从科学理论转向社会实践，从技术方法转向使用这些技术的组织与人，从系统本身转向系统与组织，环境的交互作用。（3）管理信息系统通过对整个供应链上组织内和多个组织之间的信息流管理，实现业务的整体优化，提高企业运行控制和外部交易过程的效率。前述第二个定义是人们在不断的实践中总结出来的，说明管理信息新系统的应用不仅有赖于信息技术本身，而且更多地依赖于组织的内外部环境。这是对信息系统的社会技术系统属性的充分认识。第三个定义则是近年来互联网技术的发展和电子商务深入应用的结果。管理信息系统已经突

20、破原有的界限，称谓企业内部业务流程和外部商务流程集成的平台，即跨组织的信息交流平台，管理信息系统的应用范围也已经超出了一个组织或企业的边界。由此可见，人们对管理信息系统的认识是一个不断提高和完善的过程，随着企业信息化的深入，其概念也在不断拓展和深化。11.2 课题需求提出的目的及研发的切实意义1.2.1 课题需求提出的目的随着高校扩招政策的出台,高校办学规模的不断扩大,高校教务信息量也急剧增加,开发教务管理信息系统,促进高校管理的规范化,有重要的现实意义和应用价值。排考工作日趋复杂，利于计算机排考，解决了以往排考费时费力的问题。简化了操作过程，提高教学管理效率。自动排考系统的应用必将推动教务系

21、统信息化的进程。1.2.2 研发的切实意义排考工作日趋复杂，利于计算机排考，解决了以往排考费时费力的问题。简化了操作过程，提高教学管理效率。自动排考系统的应用必将推动教务系统信息化的进程。2 系统分析2.1 需求分析超市随着现代信息技术的的发展，不可必要的要卷入信息现代化的大潮，如何使用现代化的工具，使教务效率得到提高，成为每个学校追求的目的。因此，在教务管理中引进智能排考系统，就成为时下最好的解决办法。高校教务管理水平的高低反应了高校管理水平，教务管理工作越来越追求效率与质量。传统的教务管理模式不能满足愈发复杂的教务管理工作，安排考试就是其中之一，高校每学期将组织补考等考试，任何最快，最合理

22、安排考试，直接决定了教务工作的效率。多功能排考系统应用必将推动教务系统信息化的进程。2.2 可行性分析2.2.1 经济可行性软件的经济可行性是指软件所带来的经济效益与开发所需的投资费用相比是否相适宜3。同时，还要看软件是否能给用户带来足够的经济效益。从经济效益的用钱衡量和难以用钱衡量的两个方面来考虑，本系统能减少大量的人力，节省教师的人力成本，使教师能空出时间用来教学和搞科研，能快速完成排考任务，提高了工作效率，方便管理，简化了业务流程。因此，在经济上是可行的。2.2.2 技术可行性技术可行性是对待开发的系统进行功能、性能和限制条件的分析，确定在现有技术和支持下，系统是否能够实现。系统采用VC

23、+语言编写设计，采用普遍的品的MYSQL作为后台的数据库管理，对于有简单计算机基础的人群来说很容易操作。2.2.3 管理可行性管理可行性包括法律可行性和操作使用可行性等方面的内容。法律方面主要涉及在系统开发过程中可能涉及的各种合同、侵权、责任以及各种与法律相抵触的问题。操作方面主要指系统使用单位在行政管理、工作制度和人员素质等因素上能否满足系统操作的要求，本系统无论在法律还是操作都是可行的。综上所述，销售管理系统在经济上、技术上和管理上都是可行的。 2.3 系统的软硬件介绍2.3.1系统的运行环境。 要求系统使用Visual C+设计页面，使用Visual C+ 6.0作为开发工具，使用MYS

24、QL作为数据库。操作系统是Windows XP SP2。2.3.2 开放技术 开发平台：Windows XP SP2开发工具：Microsoft Visual C+ 6.0数据库：MYSQL2.3.3 MYSQL介绍。 MySQL（发音为my ess cue el，不是my sequel）是一种开放源代码的关系型数据库管理系统（RDBMS），MySQL数据库系统使用最常用的数据库管理语言-结构化查询语言（SQL）进行数据库管理。 由于MySQL是开放源代码的，因此任何人都可以在General Public License的许可下下载并根据个性化的需要对其进行修改。MySQL因为其速度、可靠性和

25、适应性而备受关注。大多数人都认为在不需要事务化处理的情况下，MySQL是管理内容最好的选择。MySQL这个名字，起源不是很明确。一个比较有影响的说法是，基本指南和大量的库和工具带有前缀“my”已经有10年以上，而且不管怎样，MySQL AB创始人之一的Monty Widenius的女儿也叫My。这两个到底是哪一个给出了MySQL这个名字至今依然是个迷，包括开发者在内也不知道。1996年，MySQL 1.0发布,只面向一小拨人，相当于内部发布。到了96年10月，MySQL 3.11.1发布了，呵呵，没有2.x版本。最开始，只提供了Solaris下的二进制版本。一个月后，Linux版本出现了。 紧

26、接下来的两年里，MySQL依次移植到各个平台下。它发布时，采用的许可策略，有些与众不同：允许免费商用，但是不能将MySQL与自己的产品绑定在一起发布。如果想一起发布，就必须使用特殊许可，意味着要花银子。当然，商业支持也是需要花银子的。其它的，随用户怎么用都可以。这种特殊许可为MySQL带来了一些收入，从而为它的持续发展打下了良好的基础。（细想想，PostgreSQL曾经有几年限入低谷，可能与它的完全免费，不受任何限制有关系）。 MySQL3.22应该是一个标志性的版本，提供了基本的SQL支持。 MySQL关系型数据库于1998年1月发行第一个版本。它使用系统核心提供的多线程机制提供完全的多线程

27、运行模式，提供了面向C、C+、Eiffel、Java、Perl、PHP、Python以及Tcl等编程语言的编程接口（APIs），支持多种字段类型并且提供了完整的操作符支持查询中的SELECT和WHERE操作2.3.4 Microsoft Visual C+ 6.0简介 Visual C+ 6.0，简称VC或者VC6.0，是微软推出的一款C+编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。Visual C+是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工

28、具。虽然微软公司推出了 Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000、 Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。 VC+6.0Visual C+6.0不仅是一个C+ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment，IDE）。Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为

29、Developer Studio的组件集成为和谐的开发环境。2.4 系统使用开放技术介绍2.4.1 MFC 介绍 MFC (Microsoft Foundation Class Library)中的各种类结合起来构成了一个应用程序框架，它的目的就是让程序员在此基础上来建立Windows下的应用程序，这是一种相对SDK来说更为简单的方法。因为总体上，MFC框架定义了应用程序的轮廓，并提供了用户接口的标准实现方法，程序员所要做的就是通过预定义的接口把具体应用程序特有的东西填入这个轮廓。Microsoft Visual C+提供了相应的工具来完成这个工作：AppWizard可以用来生成初步的框架文件

30、（代码和资源等）；资源编辑器用于帮助直观地设计用户接口；ClassWizard用来协助添加代码到框架文件；最后，编译，则通过类库实现了应用程序特定的逻辑。如前所述，MFC实现了对应用程序概念的封装，把类、类的继承、动态约束、类的关系和相互作用等封装起来。这样封装的结果对程序员来说，是一套开发模板（或者说模式）。针对不同的应用和目的，程序员采用不同的模板。例如，SDI应用程序的模板，MDI应用程序的模板，规则DLL应用程序的模板，扩展DLL应用程序的模板，OLE/ACTIVEX应用程序的模板，等等。这些模板都采用了以文档-视为中心的思想，每一个模板都包含一组特定的类。典型的MDI应用程序的构成将

31、在下一节具体讨论。为了支持对应用程序概念的封装，MFC内部必须作大量的工作。例如，为了实现消息映射机制，MFC编程框架必须要保证首先得到消息，然后按既定的方法进行处理。又如，为了实现对DLL编程的支持和多线程编程的支持，MFC内部使用了特别的处理方法，使用模块状态、线程状态等来管理一些重要信息。虽然，这些内部处理对程序员来说是透明的，但是，懂得和理解MFC内部机制有助于写出功能灵活而强大的程序。总之，MFC封装了Win32 API，OLE API，ODBC API等底层函数的功能，并提供更高一层的接口，简化了Windows编程。同时，MFC支持对底层API的直接调用。MFC提供了一个Windo

32、ws应用程序开发模式，对程序的控制主要是由MFC框架完成的，而且MFC也完成了大部分的功能，预定义或实现了许多事件和消息处理，等等。框架或者由其本身处理事件，不依赖程序员的代码；或者调用程序员的代码来处理应用程序特定的事件。MFC是C+类库，程序员就是通过使用、继承和扩展适当的类来实现特定的目的。例如，继承时，应用程序特定的事件由程序员的派生类来处理，不感兴趣的由基类处理。实现这种功能的基础是C+对继承的支持，对虚拟函数的支持，以及MFC实现的消息映射机制。2.4.2 C/S介绍C/S 结构，即大家熟知的客户机和服务器结构。它是软件系统体系结构，通过它可以充分利用两端硬件环境的优势，将任务合理

33、分配到Client端和Server端来实现，降低了系统的通讯开销。目前大多数应用软件系统都是Client/Server形式的两层结构，由于现在的软件应用系统正在向分布式的Web应用发展，Web和Client/Server 应用都可以进行同样的业务处理，应用不同的模块共享逻辑组件；因此，内部的和外部的用户都可以访问新的和现有的应用系统，通过现有应用系统中的逻辑可以扩展出新的应用系统。这也就是目前应用系统的发展方向。（Client/Server或客户/服务器模式）：Client和Server常常分别处在相距很远的两台计算机上，Client程序的任务是将用户的要求提交给Server程序，再将Serv

34、er程序返回的结果以特定的形式显示给用户；Server程序的任务是接收客户程序提出的服务请求，进行相应的处理，再将结果返回给客户程序。 传统的C/S体系结构虽然采用的是开放模式，但这只是系统开发一级的开放性，在特定的应用中无论是Client端还是Server端都还需要特定的软件支持。由于没能提供用户真正期望的开放环境，C/S结构的软件需要针对不同的操作系统开发不同版本的软件， 加之产品的更新换代十分快，已经很难适应百台电脑以上局域网用户同时使用。而且代价高， 效率低。 C/S 结构的基本原则是将计算机应用任务分解成多个子任务，由多台计算机分工完成，即采用“功能分布”原则。客户端完成数据处理，数

35、据表示以及用户接口功能；服务器端完成DBMS的核心功能。这种客户请求服务、服务器提供服务的处理方式是一种新型的计算机应用模式。 首先必须强调的是C/S和B/S并没有本质的区别：B/S是基于特定通信协议(HTTP)的C/S架构，也就是说B/S包含在C/S中，是特殊的C/S架构。 之所以在C/S架构上提出B/S架构，是为了满足瘦客户端、一体化客户端的需要，最终目的节约客户端更新、维护等的成本，及广域资源的共享。 （1）B/S属于C/S，浏览器只是特殊的客户端； （2）C/S可以使用任何通信协议，而B/S这个特殊的C/S架构规定必须实现HTTP协议； （3）浏览器是一个通用客户端，本质上开发浏览器，

36、还是实现一个C/S系统开始2.5系统功能流程图老师输入学生补考科目输入补考科目否输入完成是按匹配算法排序显示补考顺序结束 图2.13 匹配算法介绍3.1 匹配算法介绍 算法的目的就是排出一个顺序，学生按这个顺序考试，学生都可以考试完所有科目，并且不会和考试科目相互冲突，即同一个考次不会有同一个人同多个科目。并且考试越多的人，应该越往前考试，给老师更多批改考试试卷。 匹配，一般指配合或搭配，也指结婚。“匹配”一词在不同的领域有着不同的意思，它既是数学语言，又是计算机方面的术语，其含义复杂多变。比如在字符串匹配问题上。查找模式字符串在文本中的所有出现是文本编辑软件经常要面对的一个问题。一般而言文本

37、就是要编辑的文档，而模式字符串往往由用户来指定，高效的字符串匹配 算法可以提高程序的响应性能，当然字符串匹配算法的应用远远不止于此，例如在生物计算科学中查找特定的DNA序列，也是字符串匹配算法的一个重要应用。又比如图像匹配算法在图像匹配上的应用。精确打击武器作为现代作为现代战争的的产物已经成为未来武器的发展趋势，在用于精确打击武器的景象匹配辅助导航系统中，需要利用机载图像传感器实时获取地面景象图像并与机载计算机中预先存储的二进制二维数字图像比较，确定出飞行器的当前位置，由于图像匹配的精度很高，因此可以利用这种精确的图像匹配技术消除飞行器长时间累计的误差。由于目前用于导航的定位的数字地图通常是采

38、用光学传感器获得，因此，利用卫星图像和光学图像进行匹配定位，其本质是多传感器定位。所以匹配算法具有智能适应这种复杂多变应用环境的能力。图像匹配算法的实时性也较强。 本系统采用的是匹配算法。著名匹配算法有以下一些。 1.最大匹配算法：最大匹配算法主要包括正向最大匹配算法、逆向最大匹配算法、双向匹配算法等。 其主要原理都是切分出单字串，然后和词库进行比对，如果是一个词就记录下来， 否则通过增加或者减少一个单字，继续比较，一直还剩下一个单字则终止，如果该单字串无法切分，则作为未登录处理。 2.KMP算法：kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morr

39、is同时发现，因此人们称它为克努特莫里斯普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。Next函数包含了模式串本身局部匹配的信息。 3.图像匹配算法：图像匹配是指通过一定的匹配算法在两幅或多幅图像之间识别同名点，如二维图像匹配中通过比较目标区和搜索区中相同大小的窗口的相关系数，取搜索区中相关系数最大所对应的窗口中心点作为同名点。其实质是在基元相似性的条件下，运用匹配准则的最佳搜索问题。4.KM算法 ：KM算法：（全称Kuhn-Munkras,是这两个人在1957年提出的）KM算法用来解决最大权匹配问题： 在一个二分图内，左顶点为X，右顶点为Y，

40、现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。基本原理是：该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A i ，顶点Yj的顶标为B j ，顶点Xi与Yj之间的边权为wi,j。在算法执行过程中的任一时刻，对于任一条边(i,j)，A i +Bj=wi,j始终成立3.2 KM匹配算法的C语言实现介绍 void KM() memset(linky,-1,sizeof(linky); for(int i=0;imaxn; i+) for(int j=0;jlxi) lxi=wij; /初始化顶标 for(int x

41、=0;xmaxn; x+) for(;) memset(visx,0,sizeof(visx); memset(visy,0,sizeof(visy); lack=INF; if(find(x)break; for(int i=0;i=wi,j始终成立若由二分图中所有满足A i +Bj=wi,j的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是 Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于

42、相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A i +Bj=wi,j恒成立，令A i 为所有与顶点Xi关联的边的最大权，Bj=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 1）两端都在交错树中的边(i,j)，A i +Bj的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 2）两端都不在交错树中的边(i,j)，A i 和Bj都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A i +Bj的值有