Pagini recente » Diferente pentru problema/amenzi intre reviziile 12 si 13 | Monitorul de evaluare | Diferente pentru utilizator/hrazvan intre reviziile 16 si 17 | Diferente pentru utilizator/jean intre reviziile 24 si 5 | Diferente pentru problema/rusuoaica intre reviziile 8 si 9
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="rusuoaica") ==
Rusuoaica, mare arhitecta in devenire din Manchester, a primit o tema complicata pentru ea de la facultate asa ca, evident, va cere ajutorul. Vi se da un graf neconex cu N noduri si M muchii bidirectionale cu costuri (proiectul de drumuri in constructie din tinutul iGorj, sa zicem). De altfel, puteti aplica pe graful dat operatii de tip:
* 1: platiti costul unei muchie din cele M date
* 2: creati o noua muchie intre 2 noduri oarecare platind costul A
* 3: stergeti un nod oarecare platind costul B
Rusuoaica trebuie sa determine costul minim pentru ca oricare 2 dintre nodurile ramase dupa eventuala folosire a operatiei de tip 3, sa fie conectate de un drum. (cele M muchii date nu exista, trebuie achitate cu costul dat pentru a fi create)
Ajutati-o pe Rusuoaica si spuneti-i costul total minim cerut!
Rusuoaica, mare arhitecta in devenire din Manchester, a primit o tema complicata pentru ea de la facultate asa ca, evident, va cere ajutorul. Aceasta trebuie sa proiecteze reteaua de metrou a tinutului iGorj. Se cunoaste faptul ca primaria din iGorj a construit deja N statii de metrou si a sapat M tuneluri. Totusi acestia nu au instalat sine de tren pe tunelurile sapate. De asemenea, din lipsa de fonduri, primaria nu a sapat suficiente tuneluri, astfel ca se stie ca exista cel putin doua statii de metrou care nu sunt conectate printr-un drum subteran.
In proiectarea retelei de metrou, Rusoaica poate face urmatoarele decizii:
* 1: sa amplaseze sine de tren pe un tunel deja existent, platind un cost aferent tunelului respectiv
* 2: sa construiasca un nou tunel cu sine intre 2 statii de metrou, platind costul A
* 3: sa distruga o statie de metrou, platind costul B
Este de la sine inteles ca eficienta retelei de transport conteaza mai putin decat costul de productie al acesteia. Rusuoaica trebuie astfel sa gaseasca costul minim de proiectare
al retelei astfel ca din oricare statie sa se poata ajunge in oricare alta statie folosind doar metroul.
h2. Date de intrare
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.