|
Gentili utenti mi sono appena iscritto, ed ho bisogno del vostro aiuto.
Ho da fare un progetto per un esame e vorrei qualche aiuto da voi in merito alla strategia da scegliere.
Di sicuro c'e' che devo rappresentarla tramite grafi e matrice di adiacenza, ma chiedo a voi qualche parere.
Di sotto il testo del problema.
TESTO:
Alle olimpiadi invernali è stata creata una struttura comprendente varie piste da fondo,tutte percorribili in entrambe le direzioni tramite aree di snodo.Da ogni snodo è possibile imboccare una o più piste,mentre ogni pista collega due snodi distinti disposti ai suoi due estremi (la pista non contiene altri nodi al suo interno). La struttura permette agli atleti di spostarsi da ogni snodo ad un altro snodo muovendosisempre su pista(ovvero senza togliersi gli sci dai piedi). Inoltre, il percorso da seguire peer passare da un certo snodo ad un qualunque snodoè unico per ogni coppia di snodi(in pratica la struttura non contiene cicli).
I dirigenti della televisione devono valutare dove localizzare le postazioni fisse delle telecamere , da piazzare in alcuni degli snodidella struttura, in modo da poter riprendere tutte le gare. Gli snodi vengono numerati da 1 a N, e la pista avente gli snodi i e j come estremi viene indicata tramite la coppia i,j.
Nel valutare il costo delle postazioni fisse per le telecamere, i dirigenti hanno stimato il costo di installazione per ciascun nodo(tali costi non sono necessariamente ugualie possono variare da snodo a snodo). Inoltre, per ogni pista, almeno uno tra i due snodi che essa collega deve contenere una telecamera per garantire la copertura televisiva.
Aiutate i dirigenti a identificare gli snodi che danno luogo alla copertura televisivadi costo minimo,calcolato come la somma dei costi di installazione delle telecamere in tali snodi.
Dati di Input:
La prima riga del file input.txt contiene l'intero positivo N,Il numedro di snodi della struttura.
La riga successiva contiene N interi positivi separati da uno spazio per rappresentare nell'ordine, i costi per l'installazione delle telecamere negli snodi 1,2,3,...N.
Le successive N-1 righe contengono coppie di interi positivi che rappresentano le piste. Ogni riga è composta da due interi distinti i,j separati da uno spazio, a rappresentare la pista avente gli snodi i e j come estremi. Da notare che la stessa pista non può apparire in più di una riga e l'ordine dei due interi specificati per la pista non e' significativo (i,j=j,i).
OUTPUT
output.txt= 2 righe
La prima riga deve contenere un intero positivo che appresenta il numero P di snodi che garantiscono la copertura televisivacon il minimo costo(ossia, tali snodi minimizzano la somma dei costi di installazione delle telecamere).
La seconda riga contiene P interi positivi separati da uno spazio per indicare quali sono gli snodi coinvolti in tale copertura.
Fornire una soluzion valida (Ce ne potrebbero essere più di una).Indicarne una sola.
Ultima modifica effettuata da MyNick il 10/06/2008 alle 16:39 | 
