Slalom - dubbio soluzione

Aiuto
1

Ciao forumari,

ho visto che c’è un altro topic poco sotto, ma è il problema di OP è stato risolto e non voglio andare a rompere le uova nel paniere a una storia conclusa (lol)

Il problema in questione è un minimum vertex cover su un albero con l’aggiuntiva complicazione che a ogni nodo è associato un costo. Pensavo di risolverlo semplicemente lanciando una dfs (dal nodo 1, ma essendo un albero va bene qualunque nodo < n come radice) provando a colorare (piazzare una telecamera) o meno ogni nodo e prendere la soluzione migliore, contando che se non prendo un nodo devo per forza prendere tutti i suoi figli. Memorizzo tutto in un memo, poi rilancio la dfs per stampare la soluzione.

In pseudocodice:

colora(nodo u, nodo padre, bool colore) : 
    se la soluzione per (u, colore) esiste in memo restituiscila, altrimenti:
        se colore = 0 risposta = o, altrimenti risposta = costo di u
        per ogni figlio v di u, eccetto il padre:
            se colore = 0 risposta += colora(v, u, 1)
            altrimenti risposta += min(colora(v, u, 1), colora(v, u, 0)
    memo(u, colore) = risposta
    restituisci risposta

Ho provato questa soluzione sul testcase dato e funziona, idem su un altro paio di testcase fatti da me, e non riesco a trovare alcuna falla…ma su cms prende solo il caso d’esempio, affermando che esista un costo minore di quello indicato. Potete aiutarmi? Di seguito il codice:

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g, memo;
vector<int> cost;
set<int> sol;

int dfs(int u, int color, int t)
{
    if (~memo[u][color]) return memo[u][color];

    int ans = color * cost[u];

    for (auto v : g[u]) {
        if (v != t) {
            if (color) ans += min(dfs(v, 0, u), dfs(v, 1, u));
            else ans += dfs(v, 1, u);
        }
    }

    return memo[u][color] = ans;
}

void print_sol(int u, int t)
{
    if (memo[u][0] < memo[u][1]) {
        for (auto v : g[u]) {
            if (v != t) {
                sol.emplace(v);
                print_sol(v, u);
            }
        }
    } else {
        sol.emplace(u);

        for (auto v : g[u]) if (v != t) print_sol(v, u);
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    size_t n;
    int a;
    int b;
    cin >> n, g.resize(n), cost.resize(n), memo.assign(n, vector<int>(2, -1));

    for (size_t i = 0; i < n; i++) cin >> cost[i];

    for (size_t i = 0; i < n - 1; i++) {
        cin >> a >> b, --a, --b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }

    min(dfs(0, 0, -1), dfs(0, 1, -1));
    print_sol(0, -1);
    cout << sol.size() << "\n";

    for (auto i : sol) cout << i + 1 << " ";

    cout << "\n";
    return 0;
}
2

Ciao,
praticamente l’errore si trova nella funzione print_sol: quando controlla memo[u][0] < memo[u][1] non tiene conto se il nodo precedente è stato preso oppure no e questo causa degli errori, per esempio in questo grafo:

dove i numeri sono i costi dei nodi e il nodo 1 ha costo pari a 2, la funzione inzia prendendo il nodo 1 (costo=2), poi passa al nodo 2 (costo=6), non lo prende ma prende il nodo 3 (costo=5), passa al nodo 3 e dato che memo[3][0] e memo[3][1] tengono conto solo dei figli del nodo 3 (cioè il nodo 4), ma non dei nodi 1 e 2, allora prende anche il nodo 4 pensando di non aver preso il nodo 3 (che invece è stato preso preso).

Una possibile soluzione è quella di inserire nella funzione print_sol una variabile che indichi se il nodo precendente è stato preso oppure no. Se il nodo precedente è stato preso allora indipendentemente dal fatto che memo[u][0] < memo[u][1] i nodi figli vanno presi, altrimenti si controlla se memo[u][0] < memo[u][1].

ecco il codice corretto:

#include<iostream>
#include<vector>
#include<set>
using namespace std;

vector<vector<int>> g, memo;
vector<int> cost;
set<int> sol;

int dfs(int u, int color, int t)
{
	int a, b;
	if (~memo[u][color]) return memo[u][color];

	int ans = color * cost[u];

	for (auto v : g[u]) {
		if (v != t) {
			a = dfs(v, 0, u);
			b = dfs(v, 1, u);
			
			if (color) {
				if (a < b)
					ans += a;
				else
					ans += b;
			}
			else ans += dfs(v, 1, u);
		}
	}

	return memo[u][color] = ans;
}

void print_sol(int u, int t, int mod)
{
	if (mod == 1) {
		if (memo[u][0] <= memo[u][1]) {
			for (auto v : g[u]) {
				if (v != t) {
					
					sol.emplace(v);
					print_sol(v, u, 0);
				}
			}
		}
		else {
			
			sol.emplace(u);

			for (auto v : g[u]) if (v != t) print_sol(v, u, 1);
		}
	}
	else {
		sol.emplace(u);
		for (auto v : g[u]) {
			if (v != t) {
				print_sol(v, u, 1);
			}
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	size_t n;
	int a;
	int b;
	cin >> n, g.resize(n), cost.resize(n), memo.assign(n, vector<int>(2, -1));

	for (size_t i = 0; i < n; i++) cin >> cost[i];

	for (size_t i = 0; i < n - 1; i++) {
		cin >> a >> b, --a, --b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	
	dfs(0, 0, -1);
	dfs(0, 1, -1);
	print_sol(0, -1, 1);
	cout << sol.size() << "\n";

	for (auto i : sol) cout << i + 1 << " ";
	cout << "\n";
	
	system("pause");
	return 0;
}
6 Mi Piace