Water Park Help

Ho provato a risolvere water park con una sorta di vista in profondità al contrario, invece che partire dal primo nodo, parto dagli ultimi (le piscine). So che ci sono altri modi migliori per risolverlo, ma volevo provare così. Il codice mi funziona solo quando c’è una sola uscita a ogni nodo. Qualcuno mi potrebbe spiegare perché?

#include <stdio.h>
#include <stdbool.h>
#define MAXN 100000
#include <vector>
using namespace std;

struct nodo{
    bool calc;
    float p;
    int t;
    vector<struct nodo *> prev;
}nodes[MAXN];

int n, m, p, i, a, b, mam, inde;

void calculate(nodo &a){
    if(a.calc)return;
    for(int i=0;i<a.prev.size();i++){
        calculate(*(a.prev[i]));
        a.p += (float)(a.prev[i]->p) / (float)(a.prev[i]->t);
    }
    a.calc=true;
    return;
}

int main(){
    FILE * fr, * fw;

    fr = fopen("input.txt","r");
    fw = fopen("output.txt","w");

    fscanf(fr,"%d %d %d",&n,&m,&p);
    
    for(i=0;i<m;i++){
        fscanf(fr,"%d %d",&a,&b);
        nodes[b].prev.push_back(&nodes[a]);
        nodes[a].t++;
    }

    nodes[0].p=1;
    nodes[0].calc=true;

    for(i=n-p;i<n;i++){
        calculate(nodes[i]);
    }

    for(i=n-p;i<n;i++){
        if(mam<nodes[i].p){
            mam=nodes[i].p;
            inde=i;
        }
    }

    fprintf(fw,"%d",inde);

    fclose(fr);
    fclose(fw);

    return 0;
}

Secondo me è l’idea in sè che non funziona, perchè tu qui usi una specie di DFS applicata su tutti i nodi, solo che quando hai più scivoli entranti in un nodo le probabilità si sommano e di conseguenza anche tutte le probabilità figlie si modificano, quindi ad ogni chiamata dovresti aggiornare i valori della probabilità di tutti i nodi del grafo. A livello di tempo non è fattibile, quindi io opterei per una BFS in modo tale da avere una complessità lineare nel numero di archi (fattibile dato che invece che andare subito in profondità agisce per grado di parentela rispetto alla radice).

Hai inizializzato mam come un intero…

3 Mi Piace

Ah già… Mi ero abituato a JavaScript e alle sue variabili senza tipo…

Te l’ho detto che ti avrebbe rovinato, poi ti lamenti che non vai alle nazionali.

3 Mi Piace