tramvai
Īntr-un oras linistit din America, municipalitatea a promis alegatorilor sa
construiasca linii de tramvai pe strazile orasului. Cetatenii care nu au
autoturisme sunt interesati ca strada lor sa dispuna de tramvai si cer o
despagubire din partea primariei īn cazul īn care pe strada lor nu se introduce
o astfel de linie. Cetatenii care au masini personale sunt mai interesati de
pastrarea linistii pe strada lor si cer o despagubire din partea primariei īn
cazul īn care pe strada lor va trece tramvaiul. Din fondurile CIMAU (Comisia
Internationala pentru Modernizarea Asezarilor Urbane, cu sediul in Romānia),
municipalitatea are posibilitatea sa construiasca (fara cheltuieli proprii)
legaturi directe subterane īntre oricare doua puncte ale orasului cu conditia ca
nici o linie de metrou construita sa nu coincida cu o strada.
Cerinta
Cunoscandu-se numarul de puncte (intersectii) si perechile de puncte īntre
care exista strada, despagubirea ceruta de fiecare dintre cele doua categorii de
cetateni pentru fiecare strada si stiind ca orice punct al orasului este capatul
a cel putin o strada, sa se stabileasca strazile pe care municipalitatea trebuie
sa construiasca linie de tramvai si punctele īntre care trebuie sa construiasca
linie de metrou asfel īncāt din orice punct al orasului sa se poata ajunge (cu
ajutorul mijloacelor de transport īn comun) īn orice alt punct al orasului si
costul total (rezultat din plata despagubirilor) sa fie
minim.
Date de intrare
Din fisierul tramvai.in se citesc:
- de pe
prima linie numarul n de intersectii si numarul s de strazi existente īntre
aceste intersectii, cele doua valori fiind despartite printr-un spatiu.
-
considerānd intersectiile numerotate de la 1 la n, se citesc de pe urmatoarele s
linii ale fisierului cāte 4 numere reprezentānd: cele doua numere ale
intersectiilor din capete, suma ceruta de cetatenii care nu vor tramvai pe
strada respectiva si despagubirea ceruta de cei care vor tramvai (numere
naturale de cel mult 4 cifre fiecare).
Date de iesire
Īn fisierul tramvai.out se va scrie numarul
īntreg reprezentānd costul total al despagubirilor. Daca nu exista solutii, se
va afisa īn fisier mesajul NU.
Restrictii
Exemple
tramvai.in |
tramvai.out |
5 8 |
31 |
Explicatie: daca se construiesc 4 linii de tramvai (1-5, 2-3, 2-4 si 2-5 de
exemplu) si o singura linie de metrou (3-5) se poate face legatura īntre orice
doua puncte ale orasului si costul total al despagubirilor este 31.
Timp maxim de executie/test: 0.2 secunde
prof. Rodica Pintea
Liceul de Informatica "Grigore Moisil" Bucuresti
Contact:ro_dica@yahoo.com