Ciao, sto provando a risolvere il problema barili, ma sbaglio tutti gli output ad eccezione del caso d’esempio . Ho provato qualche input in locale e mi pare funzioni. Allego il codice.
#include <bits/stdc++.h>
using namespace std;
long long int mytime = 0;
int n, m, toccati = 0;
bool vis[100050];
set< pair< int, int > > h;
vector < pair<int, int> > grafo[100050];
void ric(int nodo, int last_edge, long long risposta[])
{
if(!vis[nodo])
{
toccati++;
risposta[nodo] = mytime;
for(int i=0; i<grafo[nodo].size(); i++)
h.insert(grafo[nodo][i]);
}
if(toccati == n)
return;
vis[nodo] = true;
auto j = h.begin();
while(vis[(*j).second])
{
h.erase(j);
j=h.begin();
}
if((*j).first <= last_edge || last_edge == -1)
mytime += (*j).first;
else
mytime += toccati*((*j).first-last_edge) + last_edge;
ric((*j).second, (*j).first, risposta);
return;
}
void risolvi(int N, int M, int A[], int B[], int H[], long long risposta[]){
n = N; m = M;
for(int i=0;i<m; i++)
{
grafo[A[i]].push_back({H[i], B[i]});
grafo[B[i]].push_back({H[i], A[i]});
}
ric(1, -1, risposta);
return;
}
Il mio programma parte dal nodo 1 e aggiunge al set tutti i suoi figli. Sceglie il tubo di altezza minore. Del nuovo nodo fa’ la stessa cosa (inserisce i figli nel set). Non e’ necessario che il nuovo tubo percorso parta dall’ultimo nodo visitato, ma e’ necessario che parta da un nodo gia’ visitato (ovviamente) (e’ sempre verificato perche’ aggiungo i figli di un nodo quando lo visito per la prima volta).
Forse ho sbagliato ragionamento?
Grazie in anticipo,
Filippo.
Beh, il problema non è difficile; la chiave sta nel trovare la semplice legge che regola quanto veloce l’acqua sale; nel riconoscere che gli eventi che possono accadere sono solo due e nel costruire delle strutture dati (in realtà molto semplici) per gestirli
Sto nuovamente tentando di risolvere il problema barili, tuttavia sto riscontrando problemi con il grader:
se provo il codice in locale, va sempre in un loop infinito; se invece lo sottometto sul sito, non va in loop infinito…Qualcuno che gentilmente mi dia una mano?
Se puo’ servire allego il codice.
#include <bits/stdc++.h>
#define ii pair<int, int>
using namespace std;
int n, m, dim[100050], dad[100050], quantity[1000050];
long long int my_time=0;
bool vis[100050];
struct edge{
int a, b, w;
bool operator < (const edge &rhs)
{
return rhs.w > w;
}
};
vector <ii> grafo[100050];
vector <edge> edges;
priority_queue<int, vector <int>, greater<int> > levels;
int find_dad(int x)
{
if(dad[x] == x)
return x;
return dad[x] = find_dad(dad[x]);
}
void union_set(int first, int second)
{
int d1 = find_dad(first), d2 = find_dad(second);
if(dim[d1] > dim[d2])
{
dad[d2] = d1;
dim[d1] += dim[d2];
}
else
{
dad[d1] = d2;
dim[d2] += dim[d1];
}
return;
}
void risolvi(int N, int M, int A[], int B[], int H[], long long risposta[]){
n = N; m = M;
for(int i=0;i<m; i++){
edge a={A[i]-1, B[i]-1, H[i]}; // 0-based
edges.push_back(a);
}
for(int i=0; i<n; i++)
{
dim[i] = 1;
dad[i] = i;
}
sort(edges.begin(), edges.end());
// creating MST
for(int i=0;i<m; i++)
{
if(find_dad(edges[i].a) != find_dad(edges[i].b))
{
union_set(dad[edges[i].a], dad[edges[i].b]);
grafo[edges[i].a].push_back({edges[i].b, edges[i].w});
grafo[edges[i].b].push_back({edges[i].a, edges[i].w});
}
}
for(int i=0; i<n; i++) sort(grafo[i].begin(), grafo[i].end());
priority_queue< ii, vector < ii > , greater < ii > > pq;
for(int i=0; i<grafo[0].size(); i++)
pq.push({grafo[0][i].second, grafo[0][i].first}); // aggiungo gli archi del barile d'inizio
risposta[1] = 0; // primo barile
levels.push(0);
quantity[0] = 1;
while(!pq.empty())
{
int edge_h = pq.top().first; // arco che percorro
int nodo = pq.top().second; // nodo di arrivo
pq.pop();
for(int i=0; i<grafo[nodo].size(); i++)
if(edge_h != grafo[nodo][i].second)
pq.push({grafo[nodo][i].second, grafo[nodo][i].first}); // aggiungo gli archi uscenti del nuovo nodo di arrivo
int tot_fill = 0;// contatore per il numero di barili che porto al livello di edge_h
while(levels.top() < edge_h) // finche' dei barili collegati devono ancora essere riempiti per fa si' che l' acqua passi per l'arco edge_h
{
my_time += (edge_h - levels.top())*quantity[levels.top()]; //
tot_fill += quantity[levels.top()];
quantity[levels.top()] = 0;
levels.pop();
}
levels.push(0); quantity[0] = 1;
levels.push(edge_h); quantity[edge_h] = tot_fill;
risposta[nodo+1] = my_time;
}
return;
}
partendo dal primo barile e l’acqua inizia a riempirlo fino a che non arriva all’altezza del tubo più basso.
a quel punto l’acqua smette di salire in questo barile e va a riempire l’altro e si ripete il punto 1 …(primo evento)
(secondo evento) quando l’acqua arriva alla stessa altezza da entrambe le estremità di un tubo si può creare a partire dai due barili coinvolti un unico barile di superficie di base pari alla somma delle due e con tutti i tubi di entrambi i barili che siano collocati ad altezza superiore al tubo in questione.
da questo punto in poi l’acqua sale in questo unico contenitore fino al tubo successivo in ordine di altezza.
Non ho guardato bene il tuo codice, (non ho molta dimestichezza con le strutture dati e l’avevo fatto in C) e se hai già fatto così o intendi fare in altro modo trascura pure tutto quello che ho scritto.
Grazie per i preziosi consigli. Ti spiego la mia idea:
Creo l’mst del grafo (minimum spanning tree, l’albero la cui somma degli archi è minore possibile, dati gli archi del grafo iniziale). Successivamente utilizzo 2 priority queue con greater (utilizzando la funzione top() restituisce il minimo all’interno della priority):
usata per scegliere il prossimo arco che sarà raggiunto. Come lo scelgo? Prendo l’arco con altezza minore dalla priority queue.
usata per sapere le altezze dei barili che ho già visitato. Quando percorro un nuovo arco, porto a quel livello di acqua tutti i barili il cui livello dell’acqua è minore.
Appena visitato un nuovo barile, inserisco nella priority queue 1 tutti gli archi uscenti dal quel nodo.
Spero di essere stato chiaro e ringrazio nuovamente per la disponibilità.
Inoltre chiedevo un altro favore: potresti provare il mio codice in locale, usando il grader che si scarica dagli allegati? Perché a me da dei problemi: va in loop infiniti quando prende i dati in input .
Grazie!
Ho letto le tue idee e non mi è chiaro l’uso di un mst.
In problema come questo, dove contano le altezze dei tubi, per passare da un barile A ad un altro barile B direttamente connessi da un tubo ad altezza H1 potrebbe essere necessario fare “il giro dell’orto” perché quel tubo sta troppo in alto ed esiste un altro percorso fra i due che passa per i barili C e D collegati mediante tubi A-C C-D e D-B tutti posizionati ad altezza inferiore rispetto ad H1.
per quanto riguarda il punto 2 parli di altezze dei barili visitati ma qui interessano le superfici di base.
Per visitato intendi (facendo riferimento a quello che ti ho scritto) il fatto che si sia verificato il primo evento o anche il secondo?
comunque sul mio computer scrivendo
while(!levels.empty() && levels.top() < edge_h)
al posto di:
while(levels.top() < edge_h)
il tuo programma gira e ha risolto correttamente una decina buona di test case che mi ero fatto!
Senza il controllo sullo stato dello heap si piantava anche a me quando chiamava il metodo top di un heap vuoto.
Prova.
Quando ho risolto il problema neanche io ci avevo fatto caso inizialmente, ma l’acqua può raggiungere un barile “per la prima volta” solamente percorrendo un arco dell’ MST
Si è senz’altro vero e non ci avevo pensato neanche io, comunque nell’esempio l’acqua raggiungerà B “per la prima volta” venendo da D e non da A ovvero non tutti gli archi dell’MST verranno usati per permettere all’acqua di raggiungere un barile “per la prima volta”.
In sostanza penso che l’uso di un MST non sia sbagliato ma che se ne possa fare a meno. Quello che serve è una lista ordinata crescente dei tubi collegati ai barili già raggiunti dall’acqua e non ancora utilizzati.
Ultima riflessione in un ipotetico MST B è connesso a D o ad A?
Nel tuo esempio il MST comprenderà gli archi (A,C), (C,D), (D,B) e quindi la tua affermazione è sbagliata in quanto la soluzione corretta utilizza effettivamente tutti e soli gli archi del MST.
Inoltre vorrei aggiungere che Kruskal non è l’unico algoritmo per la costruzione del MST, esiste un altro algoritmo meno utilizzato ovvero l’algoritmo di Prim che è a mio parere più semplice di Kruskal in quanto non richiede gli UFDS. Questo algoritmo è (sebbene con qualche variante) quello che hai usato tu stesso per risolvere questo task, quindi l’utilizzo di un MST è essenziale per la risoluzione di questo problema, sebbene non ce ne accorgiamo.
Premetto che fin qui non ho mai usato un MST e non lo conosco. Ho solo avuto a che fare con STP (spanning tree protocol) e sue varianti nelle reti locali.
Grazie per il mucchio di informazione per me del tutto nuove, ne terrò conto e vedrò di documentarmi su MST, Kruskal … Comunque non sono convinto del fatto che un MST sia essenziale per la risoluzione del problema: la mia soluzione non lo usa ma funziona ugualmente (quanto meno non si da da fare per crearlo prima di iniziare la scansione).
Come ho detto prima, la tua soluzione utilizza l’algoritmo di Prim per il MST e quindi stai (senza volerlo) costruendo il MST con il solo particolare che non ti salvi il risultato da nessuna parte. Basterebbe salvarsi ogni arco percorso per ottenere proprio il MST.
Non è necessario costruirsi il MST prima di iniziare il vero e proprio algoritmo, ma comunque bisogna utilizzarlo per ottenere la soluzione finale.
A scanso di equivoci la soluzione della quale sopra si vede il codice non è la mia!
E’ quella di @spippolino01 della quale, su sua richiesta, ho solo modificato una riga dopo averla scaricata e messa sotto debug
Ho parlato della mia, in questo post, solo a grandi linee e anche Prim per me fa parte degli illustri sconosciuti.
Saluti e di nuovo grazie per le informazioni, ho di che studiare.
L’algoritmo di Prim per l’MST è di fatto molto simile all’algoritmo di Dijkstra, che immagino possa essere più simile alla tua soluzione
In questo problema, Prim si presta sicuramente meglio di Kruskal, anche se UDFS / DSU permettono spesso di risolvere anche altri problemi (e possono essere implementati in modo piuttosto compatto)
A giudicare da qui, si L’idea di accedere ai tubi in ordine di altezza coincide con quella di accedere agli archi in ordine di peso, proprio come in Prim (o in Dijkstra).
Ad ogni modo, penso che la natura fisica del problema suggerisca in modo pratico come procedere per la soluzione e che quindi non sia necessario conoscere gli algoritmi citati per poter risolvere il problema
. Ho provato qualche input in locale e mi pare funzioni. Allego il codice.
.
)
