| Fişierul intrare/ieşire: | weightgraph.in, weightgraph.out | Sursă | FMI No Stress 10 |
| Autor | Stelian Chichirim | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 323840 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Weight Graph
Se aproprie sarbatorile si trebuie sa cumperi cadouri! Se da un graf neorientat conex cu N noduri si M muchii. Tu te afli in nodul 1 si vrei sa strangi K cadouri. Definim un drum valid un drum care pleaca din nodul 1, care contine un numar arbitrar de noduri, si care nu contine 2 muchii consecutive identice. Costul unui astfel de drum este produsul valorilor muchiilor ce formeaza drumul. Numarul total de cadouri pe care le vei obtine este egal cu suma costurilor tuturor drumurilor valide din acest graf (care poate fi infinita de asemenea).
Astfel, trebuie sa ii asociati fiecarei muchii un cost mai mare sau egal ca 0 astfel incat numarul total de cadouri pe care le veti obtine sa fie exact K, iar dintre toate aceste posibile atriburi trebuie afisata o atribuire care are muchia de cost maxim minima posibila (trebuie minimizata muchia de cost maxim).
Date de intrare
Fişierul de intrare weightgraph.in contine pe prima linie N, M si K
Urmeaza M linii, fiecare avand 2 numere, Xi si Yi, care semnifica ca exista muchie de la nodul Xi la nodul Yi.
Date de ieşire
În fişierul de ieşire weightgraph.out se vor afisa M numere, fiecare pe cate o linie, astfel incat numarul de pe linia i reprezinta costul asociat muchiei dintre nodurile Xi si Yi din fisierul de intrare.
Restricţii
- 2 ≤ N ≤ 100.000
- 1 ≤ M ≤ 200.000
- 1 ≤ K ≤ N - 1
- 0 ≤ costul asociat unei muchii ≤ 10^9
- Pentru 20% din punctaj graful va avea forma de lant.
- Pentru alte 20% din punctaj N ≤ 1.000 si M ≤ 2.000.
- Pentru alte 60% din punctaj restrictiile initiale.
- Nu vor exista mai mult de o muchie intre oricare doua noduri, nici muchii de la un nod la el insusi.
- Daca exista mai multe solutii, puteti afisa oricare dintre ele.
- Se poate demonstra că, în aceste condiţii, există mereu soluţie.
Exemplu
| weightgraph.in | weightgraph.out |
|---|---|
| 5 4 4 2 3 2 4 1 2 5 1 | 1 1 1 1 |
| 5 6 3 5 3 5 4 4 2 4 3 3 1 2 1 | 1 1 0 0 1 0 |
Explicaţie
Pentru primul exemplu, drumurile valide sunt:
1->2
1->2->3
1->2->4
1->5
Toate acestea au costul 1, iar costul total va fi 4.
Am fi putut sa ii asociem muchiei (1, 2) costul 4, iar restul muchiilor costul 0, dar muchia de cost maxim (de cost 4) nu este minima posibila (muchia de cost maxim este 1 in asocierea de mai sus).
