Forum Aperto a Tutti

Soluzione super mario

Soluzione super mario

di Enrico Barberis -
Numero di risposte: 1

/*
Soluzione super mario di Barberis Enrico


Algoritmo:
          l'esrcizio camuffa il fatto che il grafo in realtà è un albero
          infatti un grafo con N nodi e con N-1 archi non potrà mai essere un grafo
         
          La soluzone diventa molto più semplice:
          basta fare una semplice visità per profondità(ho usato la ricorsione per un codice più corto)
          e appena si arriva a una foglia segnarsi la quantità di funghi raggiunta e se è maggiore
          della quantità massima totale aggiorno il massimo.
         
          Complessità: O(N)  //Spero di averla calcolata giusta
*/


#include<iostream>
#include<fstream>
using namespace std;


//Struttura del bosco: sin e des indica rispettivamente il figlio sinistro
//e il figlio destro di quel nodo dell'albero
struct zona{
       int sin;
       int des;
       int funghi;  //indica il numero di funghi di quella zona    
};


zona bosco[100000]; //Tabella di tutte le zone del bosco
int n; //Numero zone
int massimo=0;      //Numero massimo di funghi


void leggi(){
int x,y;//Variabili per la lettura
     ifstream fin("input.txt");
     fin>>n;//legggo n
     for(int i=1; i<=n; i++) fin>>bosco[i].funghi;//leggo quantità dei funghi per ogni nodo dell'albero
     for(int i=1; i<=(n-1); i++){//leggo tutti gli archi dell'albero
             fin>>x>>y;//legggo i due nodi
             //li collego(notare 0 indica che non sono collegati)
             //l'id serve per controllare che l'arco sinistra non venga riscritto da quello di destra
             if(bosco[x].sin==0) bosco[x].sin=y;
             else bosco[x].des=y;
     }   
}


//Funziona ricorsiva
//Parametro nodo: indica il nodo in cui la visita è arrivata in quel momento
//Parametro funghi: indica il numero di funghi massimo che si può ottenere fino a quel nodo
void visita(int nodo, int funghi){
     if(bosco[nodo].sin==0 && bosco[nodo].des==0){//Se sono arrivato a una foglia dell'albero
                           if(funghi > massimo) massimo=funghi;//aggiorno la quantità massima di funghi                    
     }
     else{//altrimenti se non sono in una foglia dell'albero
          //visito tutti i due figli(se esisitono) cona la quantità di funghi ottenuta fino a quel momento
          //sommata alla quantità di funghi nel nodo in cui si sta per visitare
          if(bosco[nodo].sin!=0) visita(bosco[nodo].sin,funghi+bosco[bosco[nodo].sin].funghi); 
          if(bosco[nodo].des!=0) visita(bosco[nodo].des,funghi+bosco[bosco[nodo].des].funghi);   
     }    
}


int main(){
    //Leggo dati
    leggi();
    //Inizio visita da 1 con quantià di funghi presenti nella zona 1(quella di partenza)
    visita(1,bosco[1].funghi);
    //Arrivato a questo punto la variabile out vale quanto il numero massimo di funghi ottenibile
    //stampo massimo
    ofstream fout("output.txt");
    fout<<massimo;
    fout.close();
    //Fine
    return 0;
}