Fişierul intrare/ieşire:dcmcp.in, dcmcp.outSursăSelectie echipe ACM ICPC, UPB 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1.8 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dcmcp

Sa consideram un graf neorientat avand N noduri, numerotate de la 1 la N, si M muchii. Nodul 1 corespunde unei mine de unde sunt extrase niste minerale pretioase. Nodul N corespunde unei fabrici de prelucrare a mineralelor. Fiecare muchie are asociate o durata de traversare (exprimata in unitati de timp) si o capacitate (exprimata in unitati de minerale). S-a decis ca mineralele extrase din mina sa fie transportate la fabrica folosind un singur drum. Acest drum trebuie sa aiba cea mai mare capacitate posibila, pentru a putea transporta simultan cat mai multe unitati de minerale. Capacitatea unui drum este egala cu capacitatea minima a unei muchii de pe drum. Deoarece mineralele sunt foarte sensibile, ele se vor descompune dupa T unitati de timp de la extragerea acestora din mina. Prin urmare, durata totala de traversare a drumului ales (suma duratelor de traversare ale muchiilor de pe drum) trebuie sa fie mai mica sau egala cu T.

Date de intrare

Prima linie a fisierului de intrare dcmcp.in contine un numar intreg X, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine 3 numere intregi, separate prin spatii: N, M si T. Fiecare din urmatoarele M linii va contine 4 numere intregi, separate prin spatii: A, B, C si D, avand semnificatia ca exista o muchie intre nodurile A si B, avand capacitatea C si durata de traversare D. A si B sunt numere intregi diferite intre 1 si N.

Date de iesire

Pentru fiecare din cele X teste, in ordinea din fisierul de intrare, veti afisa in fisierul de iesire dcmcp.out cate o linie continand capacitatea maxima a unui drum de la mina la fabrica, avand proprietatile cerute.

Restrictii

  • 1 ≤ X ≤ 10
  • 2 ≤ N ≤ 10 000
  • 1 ≤ M ≤ 50 000
  • 1 ≤ T ≤ 500 000
  • 1 ≤ capacitatea oricarei muchii ≤ 2 000 000 000
  • 1 ≤ durata de traversare a oricarei muchii ≤ 50 000
  • Va exista cel mult o muchie intre oricare 2 noduri.

Exemplu

dcmcp.indcmcp.out
2
2 1 10
1 2 13 10
4 4 20
1 2 1000 15
2 4 999 6
1 3 100 15
3 4 99 4
13
99
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content