2014 ACM 图论3 二部图-1

《2014 ACM 图论3 二部图-1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM程序设计实训(二)图模型——二部图华南师大讲稿问题引入GirlsandBoysZJU1137•thesecondyearoftheuniversitysomebodystartedastudyontheromanticrelationsbetweenthestudents.Therelation“romanticallyinvolved”isdefinedbetweenonegirlandoneboy.Forthestudyreasonsitisnecessarytofindoutthemaximumsetsatisfyingthecondition:th

2、erearenotwostudentsinthesetwhohavebeen“romanticallyinvolved”.Theresultoftheprogramisthenumberofstudentsinsuchaset.Theinputcontainsseveraldatasetsintextformat.Eachdatasetrepresentsonesetofsubjectsofthestudy,withthefollowingdescription:thenumberofstudentsthedescriptionofeachstudent,int

3、hefollowingformatstudent_identifier:(number_of_romantic_relations)student_identifier1student_identifier2student_identifier3...orstudent_identifier:(0)Thestudent_identifierisanintegernumberbetween0andn-1,fornsubjects.Foreachgivendataset,theprogramshouldwritetostandardoutputalinecontai

4、ningtheresult.AnexampleisgiveninFigure1.•Input•70:(3)4561:(2)462:(0)3:(0)4:(2)015:(1)06:(2)0130:(2)121:(1)02:(1)0•Output•52华南师大讲稿问题引入GirlsandBoysZJU1137thesecondyearoftheuniversitysomebodystartedastudyontheromanticrelationsbetweenthestudents.Therelation“romanticallyinvolved”isdefined

5、betweenonegirlandoneboy.Forthestudyreasonsitisnecessarytofindoutthemaximumsetsatisfyingthecondition:therearenotwostudentsinthesetwhohavebeen“romanticallyinvolved”.Theresultoftheprogramisthenumberofstudentsinsuchaset.Theinputcontainsseveraldatasetsintextformat.Eachdatasetrepresentsone

6、setofsubjectsofthestudy,withthefollowingdescription:thenumberofstudentsthedescriptionofeachstudent,inthefollowingformatstudent_identifier:(number_of_romantic_relations)student_identifier1student_identifier2student_identifier3...orstudent_identifier:(0)Thestudent_identifierisaninteger

7、numberbetween0andn-1,fornsubjects.Foreachgivendataset,theprogramshouldwritetostandardoutputalinecontainingtheresult.华南师大讲稿问题引入GirlsandBoysZJU1137Input•70:(3)4561:(2)462:(0)3:(0)4:(2)015:(1)06:(2)0130:(2)121:(1)02:(1)0•Output•52华南师大讲稿二部图与匹配匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问

8、题”中有重要作用。•假定