Buongiorno a tutti,
sto provando a risolvere funnygraph (https://training.olinfo.it/#/task/ois_funnygraph/statement) e prendo 25/100, probabilmente la mia tecnica non è corretta.
Praticamente faccio un DFS in cui:
- parto marcando tutti i nodi come non visitati;
- visito il nodo 0, di partenza, assegnandogli peso 0;
- se trovo un nodo non visitato aggiungo l’arco che collega quest’ultimo e il nodo precedente e continuo il DFS sul nuovo nodo;
- se trovo un arco che collega due nodi già visitati, e il peso dell’arco non corrisponde alla differenza dei pesi dei due nodi, non lo includo.
Ho notato che nelle assunzioni è detto questo:
• There could be more than one component between the same pair of connection points
Aspetto che volontariamente non ho considerato (e penso sia questa la causa dell’output non corretto) perché in un caso limite fra ogni coppia di nodi ci sarebbero 2 archi, dovrei quindi valutare quale dei due includere ogni volta. Perciò dovrei fare 2^\frac{MAXN}{2} tentativi.
Mi chiedevo a tal punto quale fosse il modo più efficiente per risolvere il problema.
Non ho capito bene cosa intendi, tu devi utilizzare un prefisso dei componenti quindi il primo arco tra i componenti è quello che di fatto setta la distanza.
Intendo che nel momento in cui fra due nodi ci sono più archi, devo decidere quale includere. E includere un arco piuttosto che un altro potrebbe far variare il risultato finale, perché cambierebbe il peso dei nodi successivi.
Dovrei quindi decidere, ogni volta che incontro due nodi con più archi, quale includere, e provarli tutti per ottenere il risultato migliore. Se nel percorso incontrassi ad esempio k coppie di nodi collegate da a_1, a_2 ... a_k archi , per ogni coppia dovrei fare a_i tentativi; sarebbero in totale \displaystyle\prod_{i=1}^{k} a_i tentativi, troppi per il limite di tempo.
Supponiamo l’arco i e l’arco j siano entrambi fra il nodo x ed il nodo y e che sia i <j.
Supponiamo che il grafo costruito con gli archi che precedono i sia corretto.
Se l’arco i crea un loop con potenziali scorretti fine dei controlli ed il risultato è i (0 indexed)
Se l’arco i non crea loop o ne crea uno accettabile si prosegue.
Se si arriva a piazzare l’arco j e questo ha un potenziale diverso da quello dell’arco i …
Credo che questo sia il anche il senso di ciò che diceva @frakkiobello.
Esatto, l’elenco degli archi da scegliere è un prefisso, quindi il primo che incontri ha priorità maggiore rispetto al secondo
Scusate avevo interpretato male il testo 
Non avevo capito che bisognasse includere gli archi procedendo nell’ordine in cui erano dati in input, quindi prima costruivo tutto il grafo e poi facevo una ricerca.
Ora ho risolto con un ufds, grazie.
Lo risolvi con una sola dfs? Quindi in O(N)?
No, la risolvo con UFDS (union-find disjoint set).
Il dfs lo usavo per prima, quando avevo capito male il testo.