Traffic congestion

Aiuto
1

Buonasera.

Sto provando a risolvere questo problema, ma non riesco a capire dov’è l’errore.
L’idea dell’algoritmo è quella di rappresentare le città come un albero, prendendo la prima come root, e trovando tutte le congestioni delle varie strade e prendere la minima alla fine.
Credo che ci sia qualche errore in come implemento l’albero, ma non so come correggerlo. Potete aiutarmi voi?
Questo è il codice:
#include <fstream>

#include <vector>

#include <algorithm>

#define MAXN 1000000

using namespace std;

typedef struct s{

int nd;

int sum;

int mass;


vector&lt;s*&gt; figli;



} nodo;

nodo* cities[MAXN];

int congestions[MAXN], N;


int sum(nodo* root){

int mass = 0;


for(int i=0; i &lt; root-&gt;figli.size(); i++){

    root-&gt;sum += sum(root-&gt;figli[i]);

    if(root-&gt;figli[i]-&gt;sum &gt; root-&gt;mass)
        root-&gt;mass = root-&gt;figli[i]-&gt;sum;
}

return root-&gt;sum;



}


void solve(nodo* root){

congestions[root->nd] = max(cities[0]->sum - root->sum, root->mass);

for(int i=0; i<root->figli.size(); i++)

solve(root->figli[i]);

}


int main(){

ifstream in(“input.txt”);

in >> N;


for(int i=0; i&lt;N; i++){
    cities[i] = (nodo*)malloc(sizeof(nodo));
    in &gt;&gt; cities[i]-&gt;sum;
    cities[i]-&gt;nd = i;
    cities[i]-&gt;mass = 0;
}

for(int i=0, t1, t2; i&lt;N-1; i++){
    in &gt;&gt; t1 &gt;&gt; t2;
    cities[t1]-&gt;figli.push_back(cities[t2]);
}
in.close();

sum(cities[0]);
solve(cities[0]);

ofstream out("output.txt");
out &lt;&lt; *min_element(congestions, congestions+N) &lt;&lt; "\n";
out.close();
return 0;



}

2

Almeno qualche dritta su come risolverlo?

3

Ho risolto, grazie lo stesso :slight_smile:

4

Io ho visto il post ora ahaha comunque basta fare una banale lista di adiacenza per il grafo con dei vector lol

5
Io ho visto il post ora ahaha comunque basta fare una banale lista di adiacenza per il grafo con dei vector lol

Carlo

Bè all'inizio ho provato la strada del grafo, facendo una BFS da ogni nodo. Però poi non ho visto altre soluzioni usando un grafo.. Tu come l'hai risolto?