Fişierul intrare/ieşire:sabotaj.in, sabotaj.outSursăFMI No Stress 2010
AutorVlad DutaAdăugată demarius135Dumitran Adrian Marius marius135
Timp execuţie pe test0.45 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insabotaj.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content