Data je povezana mapa n gradova sa m dvosmernih puteva. Samo dva od n
gradova A i B imaju fabriku čokolade. Posle kraćih dogovora, ljudi su odlučili
da naprave dve disjunktne povezane mreže koristeći postojećih m puteva, tako da grad
A distribuira čokoladu u svom delu, a grad B u svom delu. Svaki grad mora da
pripada tačno jednoj mreži. Ako sa WA i WB označimo ukupnu
dužinu puteva u mrežama koje sadrže A i B, potrebno je minimizirati veću od
ukupnih dužina mreža, odnosno minimizirati izraz max(WA, WB).
Za ovaj zadatak potrebno je da predate izlazne datoteke za 10 ulaznih datoteka podela.01.in,
podela.02.in, ..., podela.10.in, koji se nalaze u arhivi na računaru. Izlazi se
pamte u datoteke podela.01.out, podela.02.out, ..., podela.10.out, pri
čemu broj u nazivu izlazne datoteke odgovara broju u nazivu ulazne datoteke.
Ulaz.
U prvom redu ulaza se nalaze dva prirodna broja n i m. U drugom redu se nalaze
indeksi gradova A i B, dok se u sledećih m redova nalaze opisi puteva:
u svakom redu se nalaze tri broja x, y i z, koji označavaju da postoji
put između gradova x i y dužine z.
Izlaz.
U prvom redu izlaza se nalate dva realna broja, koji predstavljaju težine mreža koje sadrže
grad A i grad B, redom. Zatim slede kompletni opisi mreža: u sledećem redu
štampati broj gradova i broj puteva koji pripadaju mreži koja sadrži grad A, a
zatim i sve puteve iz mreže; u sledećem redu štampati broj gradova i broj puteva koji
pripadaju mreži koja sadrži grad B, a zatim i sve puteve iz mreže.
Ograničenja.
- 1 < n ≤ 500
- mapa gradova je uvek povezana
- dužine puteva su realni brojevi strogo veći od nule, a manji od 10.000
Primer 1.
podela.in
|
|
podela.out
|
6 8
1 6
1 2 3.0
1 3 3.0
2 4 2.0
2 5 2.0
3 4 1.0
4 5 3.0
4 6 1.0
5 6 4.0
|
|
5.0 2.0
3 2
1 2
2 5
3 2
3 4
4 6
|
Ocenjivanje.
Broj bodova za svaki test primer se odrešuje na sledeći način. Neka je maksimalna dužina
puteva u mrežama u vašem rešenju VAL = max(WA, WB),
a OPT je minimalna vrednost među svim takmičarskim rešenjima, uključujući i
komisijsko rešenje. Broj bodova koje dobijete se računa po formuli (zaokrugljivanje se
vrši na najmanji ceo broj koji nije manji):
1011-10·VAL⁄OPT.
Drugim rečima, ako je vaše rešenje identično sa najboljim dobijate 10 poena. U slučaju
da je rešenje 10 ili više puta veće (lošije) od najboljeg rešenja - dobićete 1 poen. Ako
je dužina puteva koju navedete u izlaznom fajlu različita od stvarne dužine puteva za
izlazne mreže - dobijate 0 poena za taj test primer.