Ciao a tutti,
sto tentando di risolvere rete idrica, 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?
#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.
