ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / USACO /

Фермер Жон фермдээ хэд хэдэн бэлчээрийн талбайтай. Үнээний жимүүд зарим бэлчээрийг тодорхой бэлчээртэй холбож нэг талбарыг үүсгэдэг. (талбайнууд нийлж талбар үүсгэнэ) Гэвч одоогийн байдлаар хоорондоо ямарч замаар холбогдоогүй дор хаяж хоёр бэлчээр байгаа бөгөөд Жоны фермийг хэд хэдэн хэсэгт хувааж байгаа билээ.

Жон доорхи шаардлагыг хангах хоёр бэлчээрийг холбох нэг зам нэмэх хүсэлтэй байгаа.

Талбар дахь бүх хос бэлчээрүүдийн хооронд дахь хамгийн богино замуудын хамгийн урт замыг талбарын “диаметр” гэнэ. 5 бэлчээрийн талбай бүхий доорхи талбарыг анхаарна уу. Бэлчээрийн талбайнууд нь үсгээр, зам нь шулуунаар тэмдэглэгдсэн байна.

              15,15   20,15

                  D       E

                  *-------*

                  |     _/|

                  |   _/  |

                  | _/    |

                  |/      |

         *--------*-------*

         A        B       C

         10,10   15,10   20,10

Энэ талбарын “диаметр” нь ойролцоогоор 12.07106, учир нь бэлчээр бүрийн хооронд дахь хамгийн богино замуудын хамгийн урт нь болох A-аас E хүрэх зам бөгөөд {A,B,E} олонлогийг үүсгэнэ. Энэ талбар дахь өөр ямар ч хоёр бэлчээрийн хооронд дахь хамгийн богино замууд дунд үүнээс урт зам байхгүй.

Ижил хавтгай дахь өөр нэг талбар нь доорхи зурагт үзүүлсэнтэй адил замуудаар холбогдсон гэж үзье.

                           *F 30,15

                         /

                       _/ 

                     _/   

                    /     

                   *------

                   G      H

                   25,10   30,10

Жоны ферм дээрх 2 зурагт үзүүлсэн шиг хоёр талбарт хуваагдсан гэж үзвэл, Жон эдгээр 2 олонлог ({A,B,C,D,E} болон {F,G,H})  тус бүрээс нэг нэг бэлчээрийг холбосон зам тавихыг хүсч байгаа бөгөөд ингэсний үр дүнд нийлсэн том талбарын {A,B,C,D,E,F,G,H}  “диаметр” нь хамгийн бага байх юм. 

Үнээний зам огтлолцохыг холбогдсон гэж үзэхгүй бөгөөд өгөгдсөн бэлчээрүүдийг холбож байгаа тохиолдолд л холбогдсон гэж үзнэ.

Оролт нь бэлчээрийн талбайн тоо, тэдгээрийн байрлал болон хоёр талбай хоорондоо үнээний замаар холбогдсон эсхийг илэрхийлэх хөрш матрицаас бүтнэ. Бэлчээрийн талбайг өөртэйгөө холбогдсон гэж үзэхгүй. Энд дээр дурьдсан бэлчээрийн талбайнуудын {A,B,C,D,E,F,G,H}  хөрш матрицыг үзүүллээ.                              

              A B C D E F G H

              A 0 1 0 0 0 0 0 0

              B 1 0 1 1 1 0 0 0

              C 0 1 0 0 1 0 0 0

              D 0 1 0 0 1 0 0 0

              E 0 1 1 1 0 0 0 0

              F 0 0 0 0 0 0 1 0

              G 0 0 0 0 0 1 0 1

              H 0 0 0 0 0 0 1 0

Оролтын өгөгдөлд оройнуудын нэр өгөгдөхгүй. Оролтонд хоорондоо ямарч дарааллаар холбогдоогүй хоёр орой (бэлчээрийн тайлбай) дор хаяж нэг байгаа.

Өгөгдсөн талбайнуудаас яг хоёр оройг шинээр холбоход шинээр нийлсэн талбарын диаметр нь бусад дурын хоёр оройг холбосноос хамгийн бага байхаар шинэ зам тавих арга ол. Тэгээд тэр хамгийн бага “диаметр”-ийг гарга.

Програмын нэр: cowtour

Оролтын формат 

Жишээ оролт (файл cowtour.in)

8

10 10

15 10

20 10

15 15

20 15

30 15

25 10

30 10

01000000

10111000

01001000

01001000

01110000

00000010

00000101

00000010 

Гаралтын формат

Гаралт нь нэг мөр байх бөгөөд шинээр холбогдсон бэлчээрийн талбайн диаметр байна. Хариултаа 6 бутархай (таслалаас хойш) оронтойгоор хэвлэ. Гаралтанд ямар нэг ойролцоолох үйлдэл бүү ашигла.

Жишээ гаралт (файл cowtour.out)

22.071068

Орчуулсан Б.Даваабаяр