Problem urgenta


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 N puncte de interes strategic şi le-au numerotat distinct de la 1 la N. Punctele de interes strategic sunt conectate prin M 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 K grupuri.

Date de intrare

Fişierul de intrare urgenta.in are următorul format:
N M K
\(i_1 j_1 p_1 \) – între punctele \(i_1\) şi \(j_1\) există o cale de acces de prioritate \(p_1\)
\(i_2 j_2 p_2 \) – între punctele \(i_2\) şi \(j_2\) există o cale de acces de prioritate \(p_2\)
...
\(i_M j_M p_M \) – între punctele \(i_M\) şi \(j_M\) există o cale de acces de prioritate \(p_M\)

Date de ieşire

Fişierul de ieşire urgenta.out va avea următorul format:
gravmax – gravitatea maximă
C – numărul de căi de acces întrerupte de calamitate
\(k_1 h_1\) – între punctele \(k_1\) şi \(h_1\) a fost întreruptă calea de acces
\(k_2 h_2\) – între punctele \(k_2\) şi \(h_2\) a fost întreruptă calea de acces
...
\(k_C h_C\) – între punctele \(k_C\) şi \(h_C\) a fost întreruptă calea de acces

Restricţii şi precizări

  • 0<N<256
  • N-2<M<32385
  • 0<K<N+1
  • Priorităţile căilor de acces sunt întregi strict pozitivi mai mici decât 256.
  • Un grup de puncte poate conţine între 1 şi N 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

General info

ID: 57

Upload: liviu

Input: urgenta.in/urgenta.out

Memory limit: 16MB/8MB

Time limit: 0.03s

Author: Marinel Şerban

Source: OJI 2002 XI-XII: Problema 1

Submissions

Special Submissions