urgenta

Time limit: 0.03s Memory limit: 16MB Input: urgenta.in Output: urgenta.out

Autorităţile dintr-o zonă de munte intenţionează să stabilească un plan de urgenţă, pentru a reacţiona mai eficient la frecventele calamităţi naturale din zonă. În acest scop au identificat NN puncte de interes strategic şi le-au numerotat distinct de la 11 la NN. Punctele de interes strategic sunt conectate prin MM căi de acces având priorităţi în funcţie de importanţă. Între oricare două puncte de interes strategic există cel mult o cale de acces ce poate fi parcursă în ambele sensuri şi cel puţin un drum (format din una sau mai multe căi de acces) ce le conectează.

În cazul unei calamităţi unele căi de acces pot fi temporar întrerupte şi astfel între anumite puncte de interes nu mai există legătură. Ca urmare pot rezulta mai multe grupuri de puncte în aşa fel încât între oricare două puncte din acelaşi grup să existe măcar un drum şi între oricare două puncte din grupuri diferite să nu existe drum.

Autorităţile estimează gravitatea unei calamităţi ca fiind suma priorităţilor căilor de acces distruse de aceasta şi doresc să determine un scenariu de gravitate maximă, în care punctele de interes strategic să fie împărţite într-un număr de KK grupuri.

Date de intrare

Fişierul de intrare urgenta.in are următorul format:
N M KN\ M\ K
i1  j1  p1i_1 \; j_1 \; p_1 – între punctele i1i_1 şi j1j_1 există o cale de acces de prioritate p1p_1
i2  j2  p2i_2 \; j_2 \; p_2 – între punctele i2i_2 şi j2j_2 există o cale de acces de prioritate p2p_2
...
iM  jM  pMi_M \; j_M \; p_M – între punctele iMi_M şi jMj_M există o cale de acces de prioritate pMp_M

Date de ieşire

Fişierul de ieşire urgenta.out va avea următorul format:
gravmax\text{gravmax} – gravitatea maximă
CC – numărul de căi de acces întrerupte de calamitate
k1  h1k_1 \; h_1 – între punctele k1k_1 şi h1h_1 a fost întreruptă calea de acces
k2  h2k_2 \; h_2 – între punctele k2k_2 şi h2h_2 a fost întreruptă calea de acces
...
kC  hCk_C \; h_C – între punctele kCk_C şi hCh_C a fost întreruptă calea de acces

Restricţii şi precizări

  • 1N2551 \leq N \leq 255
  • N1M32 384N - 1 \leq M \leq 32 \ 384
  • 1KN1 \leq K \leq N
  • Priorităţile căilor de acces sunt întregi strict pozitivi mai mici decât 256256.
  • Un grup de puncte poate conţine între 11 şi NN puncte inclusiv.
  • Dacă există mai multe soluţii, programul va determina una singură.

Exemplu

urgenta.in

7 11 4
1 2 1
1 3 2
1 7 3
2 4 3
3 4 2
3 5 1
3 6 1
3 7 5
4 5 5
5 6 4
6 7 3

urgenta.out

27
8
1 3
1 7
2 4
3 4
3 7
4 5
5 6
6 7

Log in or sign up to be able to send submissions!