Fişierul intrare/ieşire:channels.in, channels.outSursăShumen 2012 juniori
AutorGeorgi GeorgievAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test0.2 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Channels (clasa a 8-a)

In Waterland, există n lacuri (numerotate de la 1 la n) şi m canale care fac legătura între ele. Lăţimea (în metri) a fiecărui canal este cunoscută. Pe canale se poate naviga în ambele direcţii. Se ştie că o barcă cu lăţime de un metru poate naviga pe oricare canal.

Cerinţă

Scrie un program, care calculează numărul minim de canale care ar trebui să fie lărgite, astfel încât o barcă cu lăţime de k metri să poată face o excursie între fiecare două lacuri (barca poate trece de la un lac la altul dacă lăţimea sa este mai mică sau egală cu lăţimea canalului care leagă lacurile).

Date de intrare

Fişierul de intrare channels.in conţine pe prima linie numerele întregi n şi m.
Pe fiecare din următoarele m linii sunt date trei numere întregi i, j si w, care arată că există un canal de lăţime w între lacurile i şi j (1≤i, j≤n).
Pe ultima linie este dat k, întreg.

Date de ieşire

Fişierul de ieşire channels.out va conţine numărul minim de canale care ar trebui să fie lărgite.

Restricţii

  • 1 < n ≤ 1000
  • 1 < m ≤ 100000
  • 1 ≤ w ≤ 200
  • 1 ≤ k ≤ 200

Exemplu

channels.inchannels.out
6 9
1 6 1
1 2 2
1 4 3
2 3 3
2 5 2
3 4 4
3 6 2
4 5 5
5 6 4
4
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici