# Traffic congestion

**URL:** <https://forum.olinfo.it/t/traffic-congestion/3805>\
**Category:** Aiuto\
**Created:** [21 Maggio 2014, 8:15pm UTC](https://forum.olinfo.it/t/traffic-congestion/3805 "2014-05-21T20:15:21Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [21 Maggio 2014, 8:15pm UTC](https://forum.olinfo.it/t/traffic-congestion/3805/1 "2014-05-21T20:15:21Z")

</div>

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>
#defineMAXN 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;

```

}
```

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [23 Maggio 2014, 6:15pm UTC](https://forum.olinfo.it/t/traffic-congestion/3805/2 "2014-05-23T18:15:30Z")

</div>

Almeno qualche dritta su come risolverlo?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [23 Maggio 2014, 6:26pm UTC](https://forum.olinfo.it/t/traffic-congestion/3805/3 "2014-05-23T18:26:02Z")

</div>

Ho risolto, grazie lo stesso 🙂

---

<div class="post-metadata">

**Author:** ![Carlo](https://forum.olinfo.it/user_avatar/forum.olinfo.it/carlo/32/37_2.png) [@Carlo](https://forum.olinfo.it/u/Carlo)\
**Post date:** [24 Maggio 2014, 2:55pm UTC](https://forum.olinfo.it/t/traffic-congestion/3805/4 "2014-05-24T14:55:33Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [24 Maggio 2014, 3:40pm UTC](https://forum.olinfo.it/t/traffic-congestion/3805/5 "2014-05-24T15:40:07Z")

</div>

> 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?