algoritm

Por Costel si Algoritmul

== include(page="template/taskheader" task_id="algoritm") ==

Desi nu e student in anul 1 la FMI, Por Costel s-a apucat sa studieze Algoritmica Grafurilor. Astazi, el invata despre alogritmul Bellman-Ford, care calculeaza drumurile minime de la un nod sursa (in cazul de fata, nodul 1) la toate celelalte noduri intr-un graf orientat cu costuri. Por Costel, folosindu-si cunostintele sale minimale de informatica a reusit sa scrie urmatorul cod in C++ ce reprezinta o variatie al algoritmului Bellman-Ford:

Deşi nu e student în anul 1 la FMI, Por Costel s-a apucat să studieze Algoritmica Grafurilor. Astăzi, el învaţă despre alogritmul Bellman-Ford, care calculeaza drumurile minime de la un nod sursă (in cazul de faţă, nodul 1) la toate celelalte noduri într-un graf orientat, cu costuri pe muchii. Por Costel, folosindu-şi cunoştinţele sale minimale de informatică a reuşit să scrie următorul cod in C++ ce reprezintă o variaţie al algoritmului Bellman-Ford:

_for (int i=1; i <= n; ++i)_
_         d[ i ] = infinit;  		// GUITZZZ!_
_d[ 1 ] = 0;_

==code(cpp) |
for (int i = 1; i <= n; ++i)
         d[ i ] = infinit;  		// GUITZZZ!
d[ 1 ] = 0;
 
bool ok = 0;
 
while (ok == 0)
{
     ok = 1;
 
     for (int i=0; i < E.size(); ++i)      		        // OINC!
     {
           if  (d[ E[i].x ] + E[i].cost < d[ E[i].y ] )
           {
                 ok = 0;
                 d[ E[i].y ] = d[ E[i].x ] + E[i].cost;  		//Îmi place porumbul!
           }
     }
}
==

_bool ok = 0;_

Observăm mai multe deficienţe în codul de mai sus. Pe lângă documentaţia rudimentară, mai avem faptul că Por Costel işi reţine graful printr-un vector de muchii (vectorul <tex>E</tex>). O muchie este reţinută ca un triplet <tex>(x,y,cost)</tex> cu semnficiaţia că muchia porneşte de la <tex>x</tex> la <tex>y</tex> şi are costul <tex>cost</tex>. Dar cel mai rău probabil este faptul că programul este LENT !

_while (ok == 0)_
_{_
_     ok = 1;_

Pentru că vrem ca prietenul nostru cu copite sa plece cu o părere bună despre informatică, am vrea să ia 100 de puncte cu această sursă, ba chiar să ruleze cât mai repede. Este clar că numărul de iteraţii ale _while()-ului_ este influenţat direct de ordinea muchiilor in vectorul de muchii <tex>E</tex>.

_     for (int i=0; i<E.size(); ++i)         		        // OINC!_
_           if  (d[ E[i].x ] + E[i].cost < d[ E[i].y ] )_
_           {_
_                         ok = 0;_
_                         d[ E[i].y ] = d[ E[i].x ] + E[i].cost;  		//Imi place porumbul!_
_           }_
_}_
 
Observam mai multe deficiente in codul de mai sus. Pe langa documentatia rudimentara, mai avem faptul ca Por Costel isi retine graful printr-un vector de muchii (vectorul E). Dar cel mai rau probabil este faptul ca programul este LENT !
 
Pentru ca vrem ca prietenul nostru cu copite sa plece cu o parere buna despre informatica, am vrea sa ia 100 de puncte cu aceasta sursa, ba chiar sa ruleze cat mai repede. Este clar ca numarul de iteratii ale while-ului este influentat direct de ordinea muchiilor in vectorul de muchii E.
 
Dandu-se un graf orientat cu N noduri si M muchii, vi se cere sa afisati o ordonare a muchiilor astfel incat algoritmul Bellman-Ford scris de Por Costel sa se termine dupa doua iteratii (doar prima oara cand se intra in while() se produc modificari in vectorul d, iar a doua oara cand se intra, variabila ok ramane 1 si nu se mai intra a treia oara).

Dându-se un graf orientat cu <tex>N</tex> noduri şi <tex>M</tex> muchii, vi se cere să afisaţi o ordonare a muchiilor astfel incât algoritmul Bellman-Ford scris de Por Costel să se termine după exact două iteraţii (adică să se intre în instrucţiunea repetitivă _while()_ doar de două ori).

h2. Date de intrare

În fişierul de intrare $algoritm.in$ se va gasi pe prima linie <tex>T</tex>, numarul de teste.
Fiecare dintre cele T teste are formatul urmator: pe prima linie sunt doua numere <tex>N</tex> si <tex>M</tex>, numarul de noduri, respectiv numarul de muchii din graf. Urmeaza M linii ce descriu muchiile, fiecare continand exact 3 numere <tex>a</tex>, <tex>b</tex>, <tex>c</tex>, cu semnificatia ca exista o muchie de la nodul a la nodul b care are costul c.

În fişierul de intrare $algoritm.in$ se va găsi pe prima linie <tex>T</tex>, numărul de teste.
Fiecare dintre cele <tex>T</tex> teste are formatul următor: pe prima linie sunt două numere <tex>N</tex> şi <tex>M</tex>, numărul de noduri, respectiv numărul de muchii din graf. Urmează <tex>M</tex> linii ce descriu muchiile, fiecare conţinând exact 3 numere <tex>a</tex>, <tex>b</tex>, <tex>c</tex>, cu semnificaţia că există o muchie de la nodul <tex>a</tex> la nodul <tex>b</tex> care are costul <tex>c</tex>.

h2. Date de ieşire

În fişierul de ieşire $algoritm.out$ se vor afisa <tex>T</tex> linii, fiecare cu cate <tex>M</tex> numere, a i-a linie va contine p permutare a indicilor muchiilor, ce reprezinta ordinea in care vor aparea in vectorul E al lui Por Costel. Muchiile se considera indexate dupa ordinea din fisierul de intrare (e.g. prima muchie citita este muchia cu indicele 1)

În fişierul de ieşire $algoritm.out$ se vor afişa <tex>T</tex> linii, fiecare cu câte <tex>M</tex> numere, a i-a linie va conţine o permutare a indicilor muchiilor, ce reprezintă ordinea în care vor apărea în vectorul <tex>E</tex> al lui Por Costel. Muchiile se consideră indexate după ordinea din fişierul de intrare (e.g. prima muchie citită este muchia cu indicele 1).

h2. Restricţii si Precizari

* <tex>T</tex> &le; <tex>5</tex>

* <tex>1</tex> &le; <tex>N</tex> &le; <tex>10^5^</tex>
* <tex>1</tex> &le; <tex>M</tex> &le; <tex>2*10^5^</tex>
* <tex>1</tex> &le; costul unei muchii &le; <tex>10^6</tex>

* Se garanteaza ca graful este conex
* Se garanteaza ca exista cel putin o muchie din nodul 1
* infinit e definit ca fiind mai mare ca orice numar intreg
* Se accepta orice solutie care respecta cerinta
 

* Se garanteaza ca exista cel puţin o muchie care iese din nodul 1
* În programul lui Por Costel, infinit e definit ca fiind mai mare ca orice număr întreg
* Se acceptă orice soluţie care respectă cerinţa
* **Atentie!** Graful poate conţine două muchii de la <tex>x</tex> la <tex>y</tex>, sau muchie de la <tex>x</tex> la <tex>x</tex>

h2. Exemplu
table(example). |_. algoritm.in |_. algoritm.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
  4 4
  1 2 1
  3 4 2
  2 3 3
  1 3 1
| 1 4 2 3

|

h3. Explicaţie

h2. Explicatie

...

Ordinea muchiilor in vectorul E a lui Por Costel va fi în acest caz: (1, 2, 1), (1, 3, 1), (3, 4, 2), (2, 3, 3). Se poate testa că algoritmul se va finaliza în două iteraţii. Există mai multe soluţii care ar putea fi afişate. Un alt exemplu este: 1 3 4 2.

== include(page="template/taskfooter" task_id="algoritm") ==
 

== include(page="template/taskfooter" task_id="algoritm") ==

10324