package Ġchapter 4 . section 3 Ċ Ċ import Ġextensions . format Double Ċ Ċ /** Ċ Ġ* Ġ ç»Ļ å®ļ ä¸Ģ å¹ ħ åĬł æĿĥ åĽ¾ G ä»¥åıĬ å®ĥçļĦ æľĢå°ı çĶŁæĪĲ æłĳ ãĢĤ Ċ Ġ* Ġ åĲĳ G ä¸Ń æ·»åĬł ä¸ĢæĿ¡ è¾¹ e ï¼Į ç¼ĸåĨĻ ä¸Ģ æ®µ ç¨ĭåºı æī¾åĪ° e çļĦ æĿĥ éĩį åľ¨ ä»Ģä¹Ī èĮĥåĽ´ åĨħ æīį ä¼ļ è¢« åĬłåħ¥ æľĢå°ı çĶŁæĪĲ æłĳ ãĢĤ Ċ Ġ* Ċ Ġ* Ġ çĶ± ç»ĥ ä¹ł 4 . 3 . 1 5 åı¯ çŁ¥ ï¼Į e çļĦ é¡¶ çĤ¹ ä¸įåĲĮ äº§çĶŁ çļĦ çİ¯ ä¸įåĲĮ ï¼Į å½ĵ e çļĦ æĿĥ éĩį ä¸įæĺ¯ çİ¯ åĨħ çļĦ æľĢå¤§ åĢ¼ æĹ¶ æīį ä¼ļ è¢« åĬłåħ¥ æľĢå°ı çĶŁæĪĲ æłĳ ãĢĤ Ċ Ġ* Ġå°Ĩ e åĬłåħ¥ æľĢå°ı çĶŁæĪĲ æłĳ ä¸Ń ï¼Į åĨį æī¾åĪ° æĸ° æłĳ ä¸ŃçļĦ çİ¯ ï¼Į e çļĦ æĿĥ éĩį éľĢè¦ģ å°ı äºİ çİ¯ ä¸Ń æĿĥ éĩį æľĢå¤§ çļĦ è¾¹ ï¼Ī åģĩ è®¾ æĿĥ éĩį ä¸º éĿŀ è´Ł æķ° ï¼ī Ċ Ġ*/ Ċ fun Ġex 1 6 ( graph : ĠE WG , Ġm st : ĠM ST , Ġe : ĠEdge ): ĠPair < Double , ĠDouble > Ġ{ ĊĠĠĠ Ġval Ġtree Ġ= ĠEdge Weighted Graph ( graph . V ) ĊĠĠĠ Ġm st . edges (). forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġtree . add Edge ( it ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġtree . add Edge ( e ) ĊĊĠĠĠ Ġval Ġcycle Ġ= ĠEdge Weighted Graph Cycle ( tree ). cycle ()?. iterator () ĊĠĠĠ Ġcheck ( cycle Ġ!= Ġnull Ġ&& Ġcycle . hasNext ()) ĊĠĠĠ Ġvar Ġmax Edge Ġ= Ġcycle . next () ĊĠĠĠ Ġwhile Ġ( cycle . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġedge Ġ= Ġcycle . next () ĊĠĠĠĠĠĠĠ Ġif Ġ( edge Ġ> Ġmax Edge ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmax Edge Ġ= Ġedge ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġ 0 . 0 Ġto Ġmax Edge . weight Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġgraph Ġ= Ġget Tiny Weighted Graph () ĊĠĠĠ Ġval Ġm st Ġ= ĠPrim M ST ( graph ) ĊĠĠĠ Ġprintln ( mst ) ĊĊĠĠĠ Ġval Ġresult Ġ= Ġex 1 6 ( graph , Ġm st , ĠEdge ( 0 , Ġ 6 , Ġ 0 . 0 )) ĊĠĠĠ Ġprintln ("[ ${ format Double ( result . first , Ġ 2 )}, Ġ${ format Double ( result . second , Ġ 2 )} ]") Ċ }