Fişierul intrare/ieşire:flux.in, flux.outSursăSummer Challenge 2007, runda 1
AutorDin FolclorAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Flux

In oras exista N rezervoare legate intre ele prin M conducte. Rezervorul cu numarul 1 este sursa, iar rezervorul cu numarul N este destinatia. Pentru fiecare conducta se cunoaste volumul de apa care poate trece prin ea. Pentru fiecare rezervor se stie ca volumul de apa care intra in respectivul rezervor este egal cu volumul de apa care iese din respectivul rezervor (lucru care nu este valabil pentru sursa si destinatie).

In plus se mai impune urmatoarea restrictie: pentru oricare doua rezervoare i si j suma volumelor de apa ce trec prin conductele unui drum arbitrar de la i la j este constanta(este aceeasi indiferent de drum). Atentie in momentul in care se calculeaza suma daca printr-o conducta apa curge in sensul invers drumului atunci se considera cu semnul minus.

Cerinta

Calculati volumul maxim de apa care poate ajunge la destinatie intr-o astfel de retea.

Date de intrare

In fisierul de intrare flux.in se afla pe prima linie N, numarul de rezervoare. Pe a doua linie se afla M, numarul de conducte. Urmeaza apoi M linii pe care se afla triplete a b c cu semnificatia ca exista o conducta de capacitate c intre a si b.

Date de iesire

Fisierul de iesire flux.out va contine o singura linie pe care se afla volumul maxim de apa care poate ajunge la destinatie.

Restrictii

  • 2 ≤ N ≤ 100
  • 1 ≤ M ≤ 5.000
  • 0 ≤ c ≤ 10.000
  • Pentru rezultat se accepta o eroare de 10-3

Exemplu

flux.influx.out
4
6
1 3 3
2 1 3
4 3 6
2 3 3
2 4 6
1 2 2
6.500

Explicatie

Pe conducta 1 se trimite 2.5 de la 1 la 3.
Pe conducta 2 se trimite 2 de la 1 la 2.
Pe conducta 3 se trimite 3 de la 3 la 4.
Pe conducta 4 se trimite 0.5 de la 2 la 3.
Pe conducta 5 se trimite 3.5 de la 2 la 4.
Pe conducta 6 se trimite 2 de la 1 la 2.

Pentru rezervorul 2 suma cantitatilor care intra este 2+2=4 si este egala cu suma cantitatilor care ies 3.5+0.5=4.
Pentru rezervorul 3 suma cantitatilor care intra este 0.5+2.5=3 si este egala cu suma cantitatilor care ies 3.

Vom exemplifica conditia aditionala pentru cateva drumuri de la 1 la 3.

ConducteSuma
12.5
2 42 + 0.5 = 2.5
6 5 32 + 3.5 - 3 = 2.5

In ultimul exemplu conducta 3 este strabatuta de la 4 la 3 in timp ce apa curge de la 3 la 4 de aceea are semnul minus.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content