聽 International聽Olympiad聽In聽Informatics聽2008聽 August聽16聽撀�3,聽Cairo聽 聽 Contest聽Day聽1聽惵營slands聽 Proposed聽by:聽Mohamed聽Taha聽(Egypt)聽聽 聽 聽SOLUTION聽 We聽rephrase聽the聽problem聽in聽terms聽of聽graph聽theory,聽treating聽the聽islands聽as聽vertices聽and聽bridges聽as聽edges.聽 Then聽the聽condition聽of聽taking聽a聽ferry聽becomes聽that聽you聽cannot聽add聽(and聽immediately聽traverse)聽an聽edge聽to聽 a聽vertex聽that聽is聽already聽connected聽to聽your聽current聽vertex.聽 聽 Consider聽the聽connected聽components聽of聽the聽graph.聽Since聽you聽cannot聽use聽ferry聽to聽jump聽within聽a聽connected聽 component,聽 your聽 track聽 through聽 the聽 component聽 must聽 form聽 a聽 simple聽 path.聽 And聽 since聽 you聽 can聽 start聽 and聽 end聽 at聽 any聽 vertex聽 of聽 the聽 connected聽 component,聽 the聽 problem聽 reduces聽 to聽 finding聽 the聽 longest聽 weighted聽 path聽in聽each聽connected聽component.聽The聽sum聽of聽these聽values聽over聽all聽connected聽components聽gives聽the聽 desired聽answer.聽 聽 This聽becomes聽the聽longest聽path聽problem,聽which聽is聽NP恈omplete聽for聽general聽graphs.聽It聽can聽be聽done聽using聽 dynamic聽programming聽in聽O(2^E)聽time.聽To聽do聽better,聽we聽need聽to聽exploit聽the聽structure聽of聽the聽graph.聽As聽we聽 are聽dealing聽with聽connected聽components聽only,聽we聽may聽assume聽the聽graph聽is聽connected.聽 聽 It聽is聽quite聽intuitive聽to聽see,聽and聽not聽all聽that聽difficult聽to聽prove聽the聽following聽lemma:聽 (Several聽methods聽exist,聽with聽induction聽being聽the聽easiest聽and聽ugliest聽way聽to聽go.)聽 For聽any聽graph,聽any聽two聽of聽the聽following聽three聽statements聽imply聽the聽remaining聽one:聽 1.聽 the聽graph聽has聽no聽cycles聽 2.聽 the聽graph聽is聽connected聽 3.聽 the聽number聽of聽edges聽is聽1聽less聽than聽the聽number聽of聽vertices聽in聽the聽graph.聽 (And聽in聽all聽three聽cases,聽the聽graph聽in聽question聽is聽a聽tree.)聽 聽 Let聽 the聽 number聽 of聽 vertices聽 in聽 the聽 connected聽 component聽 be聽 N,聽 then聽 it聽 must聽 also聽 have聽 N聽 edges,聽 one聽 associated聽with聽each聽vertex.聽From聽the聽lemma聽we聽get聽that聽it聽must聽contain聽a聽cycle.聽However,聽if聽we聽remove聽 any聽 edge聽 on聽 the聽 cycle,聽 we聽 are聽 not聽 removing聽 any聽 connectivity,聽 as聽 any聽 walk聽 using聽 that聽 edge聽 can聽 go聽 the聽 'other聽way'聽along聽the聽cycle.聽Thus聽after聽we聽remove聽the聽edge,聽we聽get聽a聽connected聽graph聽with聽N聽vertices聽 and聽N�聽edges.聽By聽the聽lemma,聽there聽are聽no聽cycles聽left聽in聽the聽graph.聽Therefore聽the聽graph聽has聽exactly聽one聽 cycle.聽Let聽C聽be聽the聽number聽of聽vertices聽on聽the聽cycle.聽聽 聽 Note聽that聽this聽observation聽immediately聽yields聽a聽O(NC)聽solution聽for聽the聽component:聽No聽path聽can聽contain聽 all聽edges聽of聽the聽cycle.聽Thus聽for聽each聽edge聽of聽the聽cycle,聽we聽can聽try聽to聽remove聽it聽and聽calculate聽the聽diameter聽 of聽the聽resulting聽tree.聽The聽diameter聽of聽a聽tree聽on聽N聽vertices聽can聽be聽calculated聽in聽O(N).聽One聽tricky聽way聽to聽do聽 it聽is聽to聽start聽from聽any聽vertex聽A,聽find聽the聽furthest聽vertex聽B聽from聽it,聽then聽find聽the聽furthest聽vertex聽C聽from聽B,聽 and聽return聽the聽distance聽of聽B聽and聽C.聽(The聽proof聽of聽correctness聽of聽this聽algorithm聽is聽somewhat聽tricky.)聽 聽 We聽will聽now聽show聽how聽to聽get聽a聽sub恞uadratic聽solution.聽Assume聽that聽we聽label聽the聽vertices聽on聽the聽cycle聽V1聽 to聽VC,聽in聽order.聽Then聽the聽edges聽of聽the聽cycle聽are聽(V1,V2),(V2,V3)....(VC�,VC)聽and聽finally聽(VC,V1).聽If聽we聽remove聽 these聽edges,聽we聽get聽a聽cyclic聽sequence聽of聽rooted聽trees,聽one聽at聽each聽of聽the聽vertices.聽(Some聽of聽the聽trees聽can聽 just聽be聽single聽vertices.)聽 聽 There聽 are聽 2聽 cases聽 for聽 the聽 optimal聽 path:聽 either聽 it聽 lies聽 entirely聽 within聽 one聽 of聽 these聽 trees,聽 or聽 it聽 crosses聽 2聽 trees聽by聽taking聽a聽section聽of聽the聽cycle.聽We聽deal聽with聽these聽cases聽separately.聽 24聽
