Salve a tutti, sto cercando di risolvere il problema della sede centrale ma non capisco una cosa, ogni città ha una strada che la collega con le altre N-1 città giusto? oppure è tutto un percorso che va attraverso altre città?
Per esempio, avendo 4 città (A B C D), A avrebbe 3 strade (una che la collega con B, una che la collega con C e una con D), B (non contando quella che la collega con A che è già stata conteggiata) avrebbe 2 strade (una che la collega con C e una con D), C non contando le precedenti ne avrebbe una sola e quindi in totale ci sarebbero 6 strade.
Il grafo è un albero, quindi se ci sono N nodi sono presenti N-1 archi. Ogni città ha una strada che permette di visitare tutte le altre. Prova a disegnare il grafo del caso d’ esempio.
No, devono essere presenti N-1 archi.
Se ci sono 4 città (A,B,C,D) ci devono essere 3 archi che permettono alle città di essere tutte collegate( i collegamenti sono bidirezionali)
Esempio di archi:
A B
A C
B D
Grazie dell’aiuto comunque! Cioè per esempio nell’esempio che hai fatto tu per andare da C a D bisogna passare per A e B?
Ciò rende tutto molto più complicato, dovrei fare un algoritmo che mi trovi il percorso/lughezza per arrivare da ogni città ad ogni altra… Quindi in questo caso 6 percorsi
Domanda ma quesiti del genere quanto tempo danno per risolverli? E sono presenti a quale livello (scolastico, regionale etc)? Io faccio il 4° e sinceramente per risolverlo mi servirebbe almeno un paio d’ore
Esatto devi passare per quei due nodi.
Questo probelma é stato dato come allenamento per le oii (Nazionali) e in genere non devi risolvere un probelma ma un insieme di probelmi che variano da 3 a 4 ,e hai dalle 3 alle 6 ore. Ovviamente ogni competizione decide quanti probelmi e quanto tempo hai per risolverli. Io ho impiegato un 4 ore per risolverlo, é stato il primo esercizio in cui ho applicato una tecnica particolare. Se ti riferisci al tempo di esecuzione é specificato nel probelma insieme ai limiti di memoria.
Grazie moltissime! Mi hai chiarito molti dubbi!! Ultimissima domanda riguardo ai limiti di memoria, c’è un metodo particolare per vedere quanta memoria si sta usando o basta usare il task manager? Ah e ultima domanda è obbligatorio l’uso della Scanf e della printf?
Per sapere quanta memoria usi basta fare due calcoli su quanta memoria allochi. Nei problemi vengono specificati i valori massimi che possono assumere determinati dati in input e di conseguenza ti basi. Per leggere i dati in input ci sono vari modi : leggere da stdin(tastiera) o da file. Nei problemi ti specificano dove leggere i dati ma volendo puoi scegliere tu come leggerli.Se vuoi leggere da stdin anche se sei obbligato a leggere da file puoi usare freopen(“input.txt”,“r”,stdin) e freopen(“output.txt”,“w”,stdout).
Se vuoi leggere da stdin puoi usare scanf, cin. Se vuoi leggere da file fscanf oppure usare la libreria fstream. Sul forum ci sono altri post su come leggere i dati da un’occhiata.
Cioè per esempio nell’esempio che hai fatto tu per andare da C a D bisogna passare per A e B?