Min Vertex Cover per accedere ai bordi K in un albero

Question

Devo trovare il numero minimo di $ N $ vertici su un albero con $ N-1 $ Bordi, in modo che almeno $ k $ bordi di quell'albero sono collegati a questi vertici.

Ad esempio, se $ n= 9 $ e $ k= 6 $ e abbiamo questoAlbero:

   Edges  |  Vertice #1  | Vertice #2
     1            1          2
     2            1          3
     3            1          4
     4            2          5
     5            2          6
     6            3          7
     7            4          8
     8            4          9

.

La risposta giusta dovrebbe essere $ \ MathRM {min}= 2 $ .

Qualche idea?

Answer 1

C'è una $ \ mathcal {o} (NK) $ approccio DP.

Chiama un bordo coperto se selezioniamo un vertice accanto ad esso. Radice l'albero in un vertice arbitrario $ r $ . Definisci $ DP [I] [B] [T] $ come numero massimo di bordi nel sottosuolo del nodo $ i $ che può essere coperto selezionando al massimo $ T $ nodi dal sottosuolo. Se $ B= 0 $ Non siamo autorizzati a selezionare il nodo $ I $ e se $ B= 1 $ Dobbiamo selezionarlo.

Se calcolamo questo DP, possiamo risolvere il problema, come il numero minimo di nodi per coprire $ k $ bordi è la più piccola classe $ T $ per quale $ max (DP [R] [0] [T], DP [R] [1] [T]) \ Geq k $ . Nota inoltre che è sufficiente calcolare solo la classe $ DP $ per $ t \ leq k $ , come qualsiasi $ k copertura dei nodi almeno $ k $ bordi.

Per dare alla recidiva per calcolare il DP, forniamo per la prima volta la funzione di zaino: let $ k (v_ {1}, \ dots, v_ {m}) $ Sii un array in modo tale da

\ begin {equation *} K (V_ {1}, \ Dots, V_ {M}) [T]=MAX_ {T_ {1} + \ DOTS + T_ {M}= T} \ Sum_ {J= 1} ^ {M} V_ { j} [T_ {J}] \ end {equation *}

Nota che $ k (k (v_ {1}, \ dots, v_ {m-1}), v_ {m})= k (v_ {1}, \ punti, v_ {m}) $ , e quella $ k (a, b) $ può essere calcolata direttamente dalla formula di cui sopra in $ \ Mathcal {o} (| A | \ clot | B |) $ tempo. Quindi calcolo di $ k (v_ {1}, \ dots, v_ {m}) $ prende $ \ \ mathcal {o} (\ sum_ {i= 2} ^ {m} | v_ {i} | \ sum_ {j= 1} ^ {i-1} | v_ {j} |) $ tempo indipendentemente dall'ordine che ci combiniamo I set in. Se siamo interessati a solo la prima $ k $ valori del DP, la complessità scende a $ \ mathcal {o} (\ sum_ {i= 2} ^ {m} | v_ {i} | \ min (k, \ sum_ {j= 1} ^ {i-1} | v_ {j} |)) $ < / span>

Let $ c_ {i} $ Sii il set di bambini del nodo $ i $ , e $ c_ {ij} $ essere la $ j $ th figlio di $ i $ . Poi \ Begin {raccogli *} DP [I] [0] [T]= k (V_ {1}, \ Dots, V_ {| c_ {i} |}) [T] \\ DP [I] [1] [T]= | c_ {i} | + K (V '_ {1}, \ Dots, V' _ {| c_ {i} |}) [T-1] \ end {raccogli *} Dove \ Begin {raccogli *} V_ {j} [T]=max (DP [c_ {ij}] [0] [T], DP [c_ {ij}] [1] [T] + 1) \\ V '_ {J} [T]=MAX (DP [C_ {IJ}] [0] [T], DP [C_ {IJ}] [1] [T]) \\ \ end {raccogli *} Calcolo della risposta con questa ricorsione prende $ \ mathcal {o} (NK) $ tempo. Informamente questo è perché nel corso dell'algoritmo, combiniamo DPS a elemento singolo in un DP che rappresenta l'intero albero. Facciamo al massimo $ \ frac {n} {k} $ combinazioni di serie di dimensioni $ k $ , e qualsiasi elemento ci costa al massimo $ 2k $ tempo (se elemento $ x \ in un costo di $ US $ | B | $ Tempo quando calcoli $ k (a, b) $ ) Prima di essere fusi in un set di dimensioni $ k $ , quindi la quantità totale di lavoro è al massimo $ \ mathcal {o} (k ^ {2} \ frac {n} {k} + kn)=mathcal {o} (NK) $ . Questo è facile ma noioso per formalizzare con induzione.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int INF = (int)1e9 + 7;

vector<int> knapsack(const vector<int> a, const vector<int> b, int k) {
    int n = a.size();
    int m = b.size();
    vector<int> c(n+m-1, -INF);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) c[i+j] = max(c[i+j], a[i] + b[j]);
    }
    if (c.size() > k) c.resize(k);
    return c;
}

pair<vector<int>, vector<int>> dfs(int i, int p, int k, const vector<vector<int>>& g) {
    vector<int> dp0 = {0, 0};
    vector<int> dp1 = {-INF, (int)g[i].size() - (p != -1)};
    for (auto t : g[i]) {
        if (t == p) continue;
        vector<int> dp0_t, dp1_t;
        tie(dp0_t, dp1_t) = dfs(t, i, k, g);
        int m = dp0_t.size();

        vector<int> off0(m), off1(m);
        for (int j = 0; j < m; ++j) off0[j] = max(dp0_t[j], dp1_t[j] + 1);
        for (int j = 0; j < m; ++j) off1[j] = max(dp0_t[j], dp1_t[j]);
        dp0 = knapsack(dp0, off0, k+1);
        dp1 = knapsack(dp1, off1, k+1);
    }
    return {dp0, dp1};
}

int minCover(int k, const vector<vector<int>>& g) {
    vector<int> dp0, dp1;
    tie(dp0, dp1) = dfs(0, -1, k, g);
    for (int i = 0;; ++i) {
        if (max(dp0[i], dp1[i]) >= k) return i;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

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

    int t = minCover(k, g);
    cout << t << '\n';
}

.

Answer 2

Una soluzione semplice è utilizzare lo stato $ DP (n, 2, n) $ . Let $ DP (i, 0, J) $ Sii il numero massimo di bordi che possiamo ottenere usando $ \ leq j $ nodi nel sottree radicato al nodo $ i $ , con nodo $ I $ non essere nella copertura del vertice. Let $ DP (I, 1, J) $ Sii lo stesso, tranne il nodo $ I $ è incluso nel coperchio del vertice.

La transizione stessa non è ovvia, ma può essere eseguita utilizzando un metodo simile allo zaino. Considera tutti i figli del nodo $ i $ . Utilizzare tutti i valori di $ DP (CH, 0, C) $ e $ DP (CH, 1, C) $ come elementi in due zaini separati: uno per calcolare l'array full snl $ DP (I, 0) $ e uno per calcolare l'array full matrice $ DP (I, 1) $ . I costi degli articoli sono uniformemente $ c $ , mentre i valori sono i seguenti:

Se calcolo $ DP (i, 0) $ : valore di $ DP (CH, 0, c) $ è $ DP (CH, 0, c) $ ; Valore di $ DP (CH, 1, C) $ è $ DP (CH, 1, C) + 1 $ < / span>.
Se calcolando $ DP (i, 1) $ : valore di $ DP (CH, 0, c) $ $ DP (CH, 0, C) +1 $ ; Valore di $ DP (CH, 1, C) $ è $ DP (CH, 1, C) + 1 $ < / span>.

Possiamo ottenere gli array completi $ DP (I, 0) $ e $ DP (I, 1) $ direttamente dai valori di fine dei cali del raccoglitore (cioè i valori di $ kn (ultimo, j) $ per tutte le momperette Contenitore "> $ J $ ). The Knapsack ha $ o (\ # Children * n) $ Articoli per nodo ed esegue in $ o (\ # # Bambini * n * n) $ per nodo. Pertanto, la complessità totale della soluzione è $ o (n ^ 3) $ . Si prega di notare che dovrai modificare leggermente il tradizionale zaino 0-1 per prevenire due elementi che rappresentano lo stesso nodo da essere preso; Questo non è molto difficile. Inoltre, quando si calcola la classe $ DP (I, 1) $ Array, si prega di notare che il nodo $ I $ per sé è un nodo extra sul coperchio del vertice.

Sono noto sicuro che se ci sono soluzioni in esecuzione in tempo più velocemente di questa, ma non ne dubiterei.