Fire on a tree (fire)

Aiuto
1

Salve a tutti, oggi stavo provando a risolvere in maniera molto rustica il problema fire on a tree, l’attuale codice che sto usando, risolve entrambi gli esempi in un tempo anche abbastanza ragionevole, ero già consapevole che sarebbe andato out of time nella subtask 4, volevo capire però per quale ragione non riuscisse nemmeno a risolvere le subtask precedenti dove l’input è abbastanza piccolo, ringrazio in anticipo, buona giornata.

#include <iostream>
#include <fstream>
#include <vector>

struct Edge {
     int des;
};

std::vector<std::vector<Edge>> edges;
long long int dfs(int s, int starting, bool firstCall)
{
    long  long int tot = edges[s].size();
    long long int max = 1;
    if (tot <= 1) 
    {
    	if(!firstCall)
    	{
    		return 0;
    	}
    	else
    	{
    		return 1;
    	}
        
    }

    if(firstCall)
    {
        max = 0;
    }
    else
    {
        max++;
    }
    int previous = 0;
    for(auto u: edges[s])
    {
        if(u.des!=starting)
        {
            previous = dfs(u.des,s,false);
            tot = tot + previous;
            if(previous>max)
            {
                max = previous;
            }
        }
    }
    return tot - max;
}
long long int dfs(int s, int starting, bool firstCall);

int main() {
    int N;
    std::ifstream cin("input.txt");
    std::ofstream cout("output.txt");
    cin >> N;
    edges.resize(N);
    int a = 0;
    for ( int i = 0; i < N-1; ++i) 
	{
        int src;
        cin >> a;
        Edge edge;
        src = a;
        cin >> edge.des;
        edges[src].push_back(edge);
        Edge ede;
        src = edge.des;
        ede.des = a;
        edges[src].push_back(ede);
    }

    for(int i = 0; i < N; i++)
    {
        cout << dfs(i,i,true) << " ";
    }
    cout << std::endl;
    return 0;
}
2

Con questo input:

8
7 5
5 1
3 5
0 3
4 0
2 4
4 6

il programma sbaglia i nodi 0 e 3 con 3 città incendiate invece di 2 perché nel tagliare la strada che collega le altre città non tiene conto di qual è quella che preserva il maggior numero di città dal fuoco.

1 Mi Piace
3

ti ringrazio, mi è bastato riguardarlo con questo input e modificare un paio di istruzioni e ora ho 60/100, devo solo ottimizzare le tempistiche per l’out of time e dovrei aver fatto :laughing:

4

Mi aggiungo alla discussione, anche io come te raggiungo 60/100 ma non ho idea di come migliorare.
Non credo possa fare della memoization, l’unica idea che mi viene è fare pruning sulla dfs, fose in base al numero di nodi?

Ecco il mio codice:

    private static HashMap<Integer, Set<Integer>> adjList;
    private static boolean[] onFire;

    private static int spreadFire(int currCity) {
        onFire[currCity] = true;

        int citiesBurned = 0;
        int bridgeToDestroy = 0;  // bridge to destroy in order to save the adj city and minimize the damages

        int validBridges = 0;
        for (Integer nextCity : adjList.get(currCity)) {
            if (!onFire[nextCity]) {
                validBridges++;
            }
        }

        if (validBridges > 1) {  // pruning
            for (Integer nextCity : adjList.get(currCity)) {
                if (!onFire[nextCity]) {
                    int res = spreadFire(nextCity);
                    citiesBurned += res;
                    bridgeToDestroy = max(bridgeToDestroy, res);
                }
            }
        }

        onFire[currCity] = false;

        return (citiesBurned - bridgeToDestroy) + 1;  // (+1) -> at least I'm on fire
    }
5

ipotizziamo di aver calcolato la risposta a partire dal nodo 0. cosa succede se mi sposto in un nodo adiacente al nodo 0? quali valori devo ricalcolare?