Olimpiada Judeteană de Informatică
9 martie 2002, ora 900
CLASELE XI-XII
Problema 1 (Urgenta)
Autoritătile dintr-o zonă de munte intentionează să stabilească un plan de urgentă, pentru a reactiona mai eficient la frecventele calamităti 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ăti în functie de importantă. Între oricare două puncte de interes strategic există cel mult o cale de acces ce poate fi parcursă în ambele sensuri şi cel putin un drum (format din una sau mai multe căi de acces) ce le conectează.În cazul unei calamităti unele căi de acces pot fi temporar întrerupte si astfel între anumite puncte de interes nu mai există legătură. Ca urmare pot rezulta mai multe grupuri de puncte în asa fel încât între oricare două puncte din acelasi grup să existe măcar un drum si între oricare două puncte din grupuri diferite să nu existe drum.
Autoritătile estimează gravitatea unei calamităti ca fiind suma prioritătilor căilor de acces distruse de aceasta si doresc să determine un scenariu de gravitate maximă, în care punctele de interes strategic să fie împărtite într-un număr de
K grupuri.Date de intrare
Fisierul de intrare URGENTA.IN are următorul format:
N M K
i1 j1 p1 – între punctele i1 si j1 există o cale de acces de prioritate p1
i2 j2 p2 – între punctele i2 si j2 există o cale de acces de prioritate p2
...
iM jM pM – între punctele iM si jM există o cale de acces de prioritate pM
Date de iesire
Fisierul de iesire URGENTA.OUT va avea următorul format:
gravmax – gravitatea maximă
C – numărul de căi de acces întrerupte de calamitate
k1 h1 – între punctele k1 si h1 a fost întreruptă calea de acces
k2 h2 – între punctele k2 si h2 a fost întreruptă calea de acces
...
kC hC – între punctele kC si hC a fost întreruptă calea de acces
Restrictii si precizări
0<N<256
N-2<M<32385
0<K<N+1
Prioritătile căilor de acces sunt întregi strict pozitivi mai mici decât 256.
Un grup de puncte poate contine între 1 si N puncte inclusiv.
Dacă există mai multe solutii, programul va determina una singură.
Exemplu
URGENTA.IN |
URGENTA.OUT |
7 11 4
|
27 8 1 3 1 7 2 4 3 4 3 7 4 5 5 6 6 7 |
Închideti fereastra curentă pentru revenire