| Fişierul intrare/ieşire: | sabotaj.in, sabotaj.out | Sursă | FMI No Stress 2010 |
| Autor | Vlad Duta | Adăugată de |  Dumitran Adrian Marius •marius135 |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sabotaj
Firma A1-809 detine o retea formata din N calculatoare numerotate de la 1 la N conectate intre ele prin M cabluri astfel incat oricare doua calculatoare pot comunica intre ele fie direct printr-un cablu, fie prin intermediul altor calculatoare de care sunt conectate. Intre oricare doua calculatoare exista cel mult un cablu. Dumneavoastra lucrati pentru firma C-109 care se afla in concurenta cu A1-809 si aveti misiunea de a sabota reteaua acestora. Ceea ce aveti de facut este sa incercati sa taiati cateva dintre cele M cabluri care conecteaza calculatoarele, astfel incat intre cel putin doua calculatoare sa nu mai existe conexiune. Pentru a nu fi prins de paznicul nea' Fane trebuie ca timpul necesar operatiunii sa fie minim.
Cunoscand pentru fiecare cablu care este timpul necesar taierii lui, determinati care cabluri trebuie taiate pentru a rupe orice legatura intre cel putin doua calculatoare din reteaua A1-809 in cel mai scurt timp posibil.
Date de intrare
Fişierul de intrare sabotaj.in contine pe prima linie doua numere naturale N si M reprezentand numarul de calculatoare, respectiv numarul de cabluri din retea. Urmatoarele M linii contin cate trei numere naturale: x, y si t cu semnificatia ca exista un cablu care conecteaza calculatorul x de calculatorul y si a carui taiere necesita t secunde.
Date de ieşire
În fişierul de ieşire sabotaj.out se vor afisa pe prima linie doua numere: tmin si k reprezentand numarul minim de secunde necesare operatiunii precum si numarul de cabluri care trebuie taiate, in acesta ordine si separate printr-un spatiu. Urmatoarele k linii vor contine fiecare cate un numar, astfel pe cea de-a i+1-a linie din fisierul de iesire se va afla indicele celei de-a i-a muchie taiata. Muchiile se considera numerotate de la 1 la M in ordinea din fisierul de intrare si vor fi afisate in ordine crescatoare a indicelui.
Daca exista mai multe solutii toate avand acelasi timp total minim veti afisa oricare dintre ele.
Restricţii
- 2 ≤ N ≤ 200
- 1 ≤ M ≤ 3500
- 1 ≤ timpul necesar taierii unui cablu ≤ 1024
Exemplu
| sabotaj.in | sabotaj.out |
|---|---|
| 5 7 3 4 2 1 5 2 5 2 8 1 3 7 2 3 1 4 1 9 5 4 5 | 8 3 2 5 7 |
