|
Titlul: o problema Scris de: Bogdan Bondor din Februarie 17, 2010, 19:07:33 problema de fata s-a dat la concursul info-oltenia in anul 2006, eu nu am gasit o solutie pe nicaieri asa ca am scris aici. Problema suna cam asa:
Problema 2 “gripa†Într-un judeţ din Oltenia s-a anunţat prezenţa virusului gripei aviare. Pentru că oficialităţile nu ştiu deocamdată localitatea în care se află focarul, s-au gândit că, indiferent care ar fi aceasta, pot izola o zonă prin blocarea unui singur drum de acces. O zonă este formată din cel puţin o localitate. Un judeţ are cel puţin două localităţi, iar drumurile sunt bidirecţionale. Cerinţă Să se determine numărul de drumuri prin blocarea cărora (individual) să se poată izola cel puţin o zonă. Date de intrare Fişierul de intrare gripa.in conţine pe prima linie numărul n reprezentând numărul de localităţi, iar până la sfârşitul fişierului pe fiecare linie se află câte două numere separate printr-un spaţiu cu semnificaţia că există drum între cele două localităţi. Date de ieşire Fişierul de ieşire gripa.out va conţine pe prima linie 0, dacă nu poate fi izolată nici o localitate sau numărul drumurilor care pot fi blocate conform enunţului. Restricţii 1n50 Exemplu gripa.in gripa.out 7 1 1 2 1 4 2 3 3 4 4 5 5 6 5 7 6 7 Explicaţie pentru exemplu: drumul dintre localităţile 4 şi 5 conduce la izolarea unei zone. Timp maxim de execuţie: 1 secundă/test Va multumesc pentru ajutor. Titlul: Răspuns: o problema Scris de: Mircea Dima din Februarie 17, 2010, 20:26:25 Problema cred ca cere defapt determinarea muchiilor critice http://infoarena.ro/problema/biconex
|