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

Vezi solutiile trimise | Statistici

Irmcast

Sa consideram o retea de comunicatie ce consta din N noduri numerotate de la 1 la N. Nodurile sunt interconectate in asa fel incat reteaua are structura unui arbore avand radacina in nodul 1. Nodul 1 doreste sa trimita un mesaj (acelasi mesaj) catre fiecare nod care este o frunza in arbore (adica nu are nici un fiu) - aceasta operatie este cunoscuta sub numele de multicast. Un mesaj poate fi transmis numai de la un nod la unul din descendentii acestuia (inclusiv nodul insusi). Fiecare muchie a arborelui are asociat un cost, iar costul transmiterii unui mesaj de la un nod X la unul din descendentii acestuia este suma costurilor muchiilor de pe drumul unic de la X la Y (daca X = Y, atunci costul este 0). Costul total al unei strategii de multicast este egal cu suma costurilor transmiterii fiecarui mesaj.
Pentru a-si indeplini scopul, nodul 1 va utiliza urmatoarea strategie de multicast: Strategia consta din K runde intermediare. In prima runda, nodul 1 trimite un mesaj individual catre o submultime de noduri S1, astfel incat fiecare nod frunza din arbore este descendent al exact unui singur nod X din S1 (aceasta inseamna ca orice nod X din S1 nu este descendent al unui alt nod Y din S1). In runda i (2 ≤ i ≤ K), fiecare nod X din Si-1 trimite un mesaj individual unei submultimi de noduri Si,X din subarborele sau, in asa fel incat fiecare nod frunza care este descendent al lui X este descendent al exact unui singur nod din Si,X. Submultimea de noduri Si este reuniunea multimilor Si,X, pentru fiecare X din Si-1. La final, fiecare nod X din SK trebuie sa trimita un mesaj individual fiecarui nod frunza care este descendent al lui X.
Fiind data reteaua de comunicatie, costul fiecarei muchii si numarul de runde intermediare K, determinati costul total minim al unei strategii de multicast.

Date de intrare

Prima linie a fisierului de intrare irmcast.in contine numarul intreg T, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine 2 numere intregi, separate printr-un spatiu, N si K. Urmatoarele N-1 linii contin cate 3 numere intregi fiecare: A, B si C, avand semnificatia ca nodul B este un fiu al nodului A, iar muchia (A,B) are costul C.

Date de iesire

Pentru fiecare din cele T teste date in fisierul de intrare, afisati in fisierul de iesire irmcast.out cate o linie continand costul total minim al unei strategii de multicast avand proprietatile specificate.

Restrictii

  • 1 ≤ T ≤ 21
  • 1 ≤ N ≤ 333
  • 1 ≤ K ≤ 10
  • 1 ≤ costul oricarei muchii ≤ 10 000

Exemplu

irmcast.inirmcast.out
1
6 1
1 2 10
1 3 11
2 4 21
2 5 17
3 6 7
66

Explicatie

In prima (si singura) runda intermediara, nodul 1 trimite mesaje nodului 6 (cu costul 18) si nodului 2 (cu costul 10). Multimea S1 este {2,6}. La final, nodul 6 va trimite un mesaj catre el insusi (cu costul 0), iar nodul 2 va trimite mesaje nodului 4 (cu costul 21) si nodului 5 (cu costul 17). Costul total este 18+10+21+17=66.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content