2014 ACM 图论3 二部图-p1

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

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

2、entsinthesetwhohavebeen“romanticallyinvolved”.Theresultoftheprogramisthenumberofstudentsinsuchaset.Theinputcontainsseveraldatasetsintextformat.Eachdatasetrepresentsonesetofsubjectsofthestudy,withthefollowingdescription:thenumberofstudentsthedescriptionofeachstudent,inthefollowingformatstudent_ident

3、ifier:(number_of_romantic_relations)student_identifier1student_identifier2student_identifier3...orstudent_identifier:(0)Thestudent_identifierisanintegernumberbetween0andn-1,fornsubjects.Foreachgivendataset,theprogramshouldwritetostandardoutputalinecontainingtheresult.AnexampleisgiveninFigure1.•Inpu

4、t•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”isdefinedbetweenonegirlandoneboy.Forthestudyreasonsitisnecessarytofin

5、doutthemaximumsetsatisfyingthecondition:therearenotwostudentsinthesetwhohavebeen“romanticallyinvolved”.Theresultoftheprogramisthenumberofstudentsinsuchaset.Theinputcontainsseveraldatasetsintextformat.Eachdatasetrepresentsonesetofsubjectsofthestudy,withthefollowingdescription:thenumberofstudentsthed

6、escriptionofeachstudent,inthefollowingformatstudent_identifier:(number_of_romantic_relations)student_identifier1student_identifier2student_identifier3...orstudent_identifier:(0)Thestudent_identifierisanintegernumberbetween0andn-1,fornsubjects.Foreachgivendataset,theprogramshouldwritetostandardoutpu

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