Leggere gli input del grafico per un puzzle di programmazione e poi risolverlo

Question

Leggere gli input del grafico per un puzzle di programmazione e poi risolverlo

#1 da (1 voti)

1

Ho appena fatto una domanda sulla competizione di programmazione e l'ho assolutamente bombardata. Ho avuto problemi fin dall'inizio stesso dalla lettura del set di input. La domanda era fondamentalmente una variante di questo puzzle link ma aveva anche un componente orario nella prima riga (diciamo 3 ore dopo l'inizio di evacuazione). Si legge così

Questo puzzle è un tributo a tutte le persone che hanno sofferto del terremoto in Giappone. L'obiettivo di questo puzzle è, data una rete di strade e luoghi, determinare il numero massimo di persone che possono essere evacuate.

Le persone devono essere evacuate dai punti di evacuazione ai punti di soccorso. Viene fornito l'elenco delle strade e il numero di persone che possono trasportare per ora.

Specifiche di input Il tuo programma deve accettare un solo argomento della riga di comando: il file di input. Il file di input è formattato come segue: la prima riga contiene 4 numeri interi nrstn è il numero di posizioni (ogni posizione è data da un numero da 0 a n-1) r è il numero di strade s è il numero di posizioni da evacuare da (punti di evacuazione) t è il numero di luoghi in cui le persone devono essere evacuati (punti di salvataggio) la seconda riga contiene numeri interi che forniscono le posizioni dei punti di evacuazione; la terza riga contiene t interi che danno le posizioni dei punti di salvataggio le linee contengono le definizioni stradali. Ogni strada è definita da 3 numeri interi l1 l2 larghezza dove l1 e l2 sono le posizioni collegate dalla strada (le strade sono a senso unico) e la larghezza è il numero di persone all'ora che può stare sulla strada

Ora guarda il set di input di esempio

Il 3 nella prima riga è il componente aggiuntivo ed è definito come il numero di ore da quando è iniziato il resuce, che in questo caso è 3.

Ora la mia soluzione era usare l'algoritmo Dijisktras per trovare il percorso più breve tra ciascuno dei nodi di salvataggio ed evac. Ora il mio problema è iniziato con la lettura del set di input. Ho letto la prima riga in python e ho memorizzato i valori nelle variabili. Ma poi non sapevo come memorizzare i valori della distanza tra i nodi e cosa DS usare e come inserirlo per dire un'implementazione standard dell'algoritmo dijikstras.

Quindi la mia domanda è due volte 1.) Come prendo l'input di tali problemi? - Ho affrontato questo problema recentemente in alcune competizioni e spero di poter ottenere un semplice frammento di codice o una spiegazione in java o python per leggere il set di input dei dati in modo tale da poterlo inserire come algoritmo grafico / grafico come dijikstra e floyd / warshall. Anche una soluzione al problema precedente sarebbe di aiuto.

2.) Come risolvere questo enigma? Il mio algoritmo era:

Trova il percorso più breve tra i punti evac (nell'esempio sopra riportato è 14 da 0 a 3) Moltiplicalo per numero di ore per ottenere il numero massimo di salvataggi Anche la risposta data per la variante per il set di input era 24 che non capisco. Qualcuno può spiegarlo anche.

UPDATE:

Ottengo come la risposta è 14 nel link problema dato - sembra essere solo il percorso più breve tra i nodi 0 e 3. Ma con il componente 3 ore come è la risposta 24

UPDATE

Ho capito com'è 24 - è un traversal grafico completo ad ogni ora e questo è il modo in cui lo risolvo

Hour 1
Node 0 to Node 1 - 10 people
Node 0 to Node 2- 5 people
TotalRescueCount=0
Node 1=10
Node 2= 5

Hour 2
Node 1 to Node 3 = 5(Rescued)
Node 2 to Node 4 = 5(Rescued)
Node 0 to Node 1 = 10
Node 0 to Node 2 = 5 
Node 1 to Node 2 = 4
TotalRescueCount = 10
Node 1 = 10
Node 2= 5+4 = 9

Hour 3
Node 1 to Node 3 = 5(Rescued)
Node 2 to Node 4 = 5+4 = 9(Rescued)
TotalRescueCount = 9+5+10 = 24

È abbastanza difficile per questo caso, per i vari evac e punti di salvataggio come posso scrivere un pgm per questo?

java python puzzles

posta Slartibartfast 28.06.2012 - 17:44

fonte

1 risposta

Leggi altre domande sui tag java python puzzles

Dovrei fornire fallback per elementi HTML5 / CSS3 in una pagina web a questo punto? Confusione continua su ivar e proprietà nell'obiettivo C

score 1 · Accepted Answer

Questa domanda è fondamentalmente duplice:

Come risolvi il problema attuale? e
Come leggi generalmente i dati del grafico?

La prima domanda è un po 'stretta e sembra che la seconda sia più interessante per te nel lungo periodo. Quindi, permettimi di indirizzarti agli algoritmi di flusso . È un passo avanti rispetto a Dijkstra in termini di complessità di implementazione, ma come hai già capito, c'è così tanto che puoi fare con un singolo percorso. I flussi di rete sono una cosa completamente diversa.

Per quanto riguarda la lettura del tuo input, dipende in modo significativo dal tipo di libreria di grafici che desideri utilizzare. Alcuni anni fa, quando ero attivo in queste competizioni, non ci è stato consentito utilizzare librerie di terze parti, quindi abbiamo dovuto implementare le nostre implementazioni.

In tal caso, è necessario pensare in anticipo se si desidera leggere in una matrice completa o se si desidera mantenere il grafico come elenco di adiacenza. Queste sono le due strutture dati più importanti da conoscere per gli algoritmi del grafico. (più precisamente, spesso non hai bisogno di pensare al futuro, perché le specifiche di input del problema ti indirizzano verso l'una o l'altra)

L'input di lettura per una matrice di adiacenza è semplice come due cicli for nidificati. Nel corpo del ciclo interno, si legge semplicemente un valore e lo si assegna a una cella della matrice. Fatto.

Per gli elenchi di adiacenze è necessario preparare l'elenco dei vicini di un nodo per ciascuno dei nodi, ovvero per n nodi si prepara un elenco di dimensioni n che contiene un elenco vuoto per ogni voce. Quindi avete di nuovo due for-loop annidati: il ciclo esterno passa sopra i nodi, il ciclo interno legge i vicini di quel nodo e li aggiunge alla lista interna corrispondente. Voila: una rappresentazione della lista di adiacenza del grafico.

Un'aggiunta importante per programmare sfide / competizioni: assicurati di sapere nei tuoi sogni come scrivere entrambe le varianti prima e persino di pensare alla competizione. Ci sono domande di esempio illimitate e siti di pratica là fuori. Cerca in giro per problemi con l'input grafico, quindi scrivi e riscrivi il codice di input ancora e ancora. Dovrebbe quasi sempre essere quasi lo stesso codice, e una volta che ci si è abituati, la lettura in input come quella che hai dato sopra richiede 5 minuti al massimo . Se vuoi competere con i giocatori molto forti in quel campo, dovresti essere in grado di codificare l'input per questo entro un minuto o meno.