Pagina principala | Inscriere | Autentificare | Probleme | Runde | Clasament | Anunturi | Echipa | Regulament | Exit


Vizualizare problema: tramvai

Titlul problemei tramvai
Grupa Grupa B
Problema numarul 1
Runda numarul 5
Timp de executie (ms) 200
Punctaj maxim pentru problema 50
Dimensiunea maxima a segmentului de date (MB) 15
Dimensiunea maxima a stivei (MB) 1
Profesorul care a propus problema Rodica Pintea
Enuntul problemei
Ī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.
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.
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 (n<=100, s<=5000).
- 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).
Ī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.
Exemplu:
tramvai.in
5 8
1 2 10 4
2 3 5 8
3 4 7 2
2 4 5 10
1 4 7 2
2 5 5 3
5 1 3 8
4 5 12 7
tramvai.out
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.

Click aici pentru a va intoarce

© 2002 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com