# Rete idrica (tubature)

**URL:** <https://forum.olinfo.it/t/rete-idrica-tubature/4838>\
**Category:** Aiuto\
**Created:** [28 Ottobre 2017, 5:06pm UTC](https://forum.olinfo.it/t/rete-idrica-tubature/4838 "2017-10-28T17:06:22Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [28 Ottobre 2017, 5:06pm UTC](https://forum.olinfo.it/t/rete-idrica-tubature/4838/1 "2017-10-28T17:06:22Z")

</div>

Ciao a tutti,  
sto tentando di risolvere [rete idrica](https://training.olinfo.it/#/task/fri_tubature/statement), ma tutti i miei tentativi mi hanno portato solo ad un misero 25/100 con almeno un caso errato dal terzo subtask in poi. La mia idea è di percorrere l’albero dal fondo tenendomi il numero minimo di guardie per ogni nodo, tuttavia non sembra avere molto successo. Qualcuno può darmi un aiutino?

```auto
#include <forward_list>
#include <queue>
#define MAXN 100000

using namespace std;

int citta[MAXN];
int guardie[MAXN];
forward_list<int> ordine;
forward_list<int> grafo[MAXN];

int pianifica(int N, int M, int da[], int a[], int C[], int G[])
{
    int root = N-1;
    for(int i=0; i!=N-1; i++)
    {
        grafo[da[i]].emplace_front(a[i]);
        root ^= a[i]^i;
    }
    for(int i=0; i!=M; i++)
        citta[C[i]]++;

    queue<int> coda; coda.emplace(root);
    while(!coda.empty())
    {
        int now = coda.front();
        coda.pop();
        ordine.emplace_front(now);

        for(int i : grafo[now])
            coda.emplace(i);
    }

    for(int i : ordine)
    {
        if(grafo[i].empty())
        {
            guardie[i] = G[i];
            continue;
        }
        for(int j : grafo[i])
        {
            citta[i] += citta[j];
            if(citta[j]) guardie[i] += guardie[j];
        }
        guardie[i] = min(guardie[i],G[i]);
    }

    return guardie[root];
}

```

Grazie in anticipo.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [22 Giugno 2023, 5:42pm UTC](https://forum.olinfo.it/t/rete-idrica-tubature/4838/2 "2023-06-22T17:42:39Z")

</div>

Come non detto, ho risolto! [😊](https://www.youtube.com/watch?v=j5a0jTc9S10)