Min Vertex Cover pour accéder aux bords K dans un arbre

Question

J'ai besoin de trouver le nombre minimum de $ n $ sommets sur un arbre avec $ n-1 $ bords, de sorte que au moins $ k $ bords de cet arbre sont connectés à ces sommets.

Par exemple, si $ n= 9 $ et $ k= 6 $

   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 bonne réponse doit être $ \ mathrm {min}= 2 $ .

.

Toutes les pensées?

Answer 1

Il y a une $ \ mathcal {o} (nk) $ approche DP.

Appeler un bord couvert si nous sélectionnons un sommet à côté de celui-ci. Racine l'arbre à un sommet arbitraire $ R $ . Définir $ dp [i] [b] [t] $ comme nombre maximal d'arêtes dans le sous-arbre de noeud $ i $ qui peut être couvert en sélectionnant au plus $ t $ nœuds de la sous-arbre. Si $ B= 0 $ Nous ne sommes pas autorisés à sélectionner le nœud $ i $ , et si $ b= 1 $ Nous devons le sélectionner.

Si nous calculons ce PDD, nous pouvons résoudre le problème, car le nombre minimal de nœuds pour couvrir k $ k $ est la plus petite $ T $ pour lequel $ max (dp [r] [0] [t], dp [r] [1] [t]) \ geq K $ . Notez plus loin qu'il suffit de calculer uniquement la $ DP $ pour $ t \ leq k $ , comme tout $ k couvre des nœuds au moins $ K $ bords.

Pour donner à la récurrence de calculer le DP, nous donnons d'abord la fonction Knapsack: laissez $ k (v_ {1}, \ dots, v_ {m}) $ Soyez un tableau tel que

\ commence {équation *} K (v_ {1}, \ dots, v_ {m}) [t]=max_ {t_ {1} + \ dots + t_ {m}= t} \ sum_ {j= 1} ^ {m} v_ { j} [t_ {j}] \ fin {équation *}

Notez que $ k (k (v_ {1}, \ dots, v_ {m-1}), v_ {m})= k (v_ {1}, \ Dots, v_ {m}) $ , et que $ k (a, b) $ peut être directement calculé par la formule ci-dessus dans $ \ mathcal {o} (| A | \ CDOT | B |) $ temps. Par conséquent, calculer $ k (v_ {1}, \ dots, v_ {m}) $ prend $ \ mathcal {o} (\ sum_ {i= 2} ^ ^ {m} | v_ {i} | \ sum_ {j= 1} ^ {i-1} | v_ {j} |) $ temps quelle que soit la commande que nous combinons Les ensembles de. Si nous ne sommes intéressés que par le premier $ K $ valeurs du DP, la complexité tombe sur $ \ mathcal {o} (\ sum_ {i= 2} ^ {m} | v_ {i} | \ min (k, \ sum_ {j= 1} ^ {i-1} | v_ {j} |)) $ < / span>

let $ C_ {i} $ $ Soyez l'ensemble des enfants de nœud $ i $ , et $ c_ {ij} $ est la $ j $ 00 enfant de $ i $ . Puis \ commence {rassembler *} Dp [i] [0] [t]= k (v_ {1}, \ dots, v_ {| c_ {i} |}) \\ \\ Dp [i] [1] [t]= | c_ {i} | + K (v '_ _ {1}, \ dots, v' _ {| c_ {i} |}) [T-1] \ fin {rassembler *} Où \ commence {rassembler *} 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]) \\ \ fin {rassembler *} Calcul de la réponse avec cette récursion prend $ \ mathcal {o} (nk) $ temps. De manière informelle, cela est dû au cours de l'algorithme, nous combinons des DPS à élément unique dans un DP représentant l'arbre entier. Nous faisons au plus $ \ frac {n} {k} $ combinaisons d'ensembles de taille $ k $ et tout élément nous coûte au plus 2k $ temps (si élément $ x \ dans un $ coûts US $ | b | $ temps lors du calcul de $ k (a, b) $ ) avant qu'il ne soit fusionné dans un ensemble de taille $ k $ , de sorte que la quantité totale de travail est au plus $ \ mathcal {o} (k ^ {2} \ frac {n} {k} + kn)=mathcal {o} (nk) $ . C'est facile mais fastidieux de formaliser avec induction.

#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

Une solution simple consiste à utiliser l'état $ dp (n, 2, n) $ . Laissez $ DP (i, 0, j) $ Soyez le nombre maximum d'arêtes que nous pouvons obtenir en utilisant $ \ Leq j $ nœuds dans le sous-arbre enraciné au nœud $ i $ , avec noeud $ i $ elle-même ne pas être dans la couverture de sommet. Laissez $ dp (i, 1, j) $ être identique, sauf le noeud $ i $ est inclus dans la couverture de sommet.

La transition elle-même n'est pas évidente, mais elle peut être faite à l'aide d'une méthode de type sac à dos. Considérez tous les enfants du nœud $ I $ . Utilisez toutes les valeurs de $ DP (ch, 0, c) $ et $ DP (ch, 1, c) $ $ comme éléments dans deux knapacks distincts: un pour calculer le tableau complet $ dp (i, 0) $ et un pour calculer le tableau complet $ DP (I, 1) $ . Les coûts des éléments sont uniformément $ C $ , tandis que les valeurs sont les suivantes:

Si Calculer $ DP (I, 0) $ : valeur de $ DP (ch, 0, c) $ $ est $ DP (ch, 0, c) $ ; Valeur de $ DP (ch, 1, c) $ est $ DP (ch, 1, c) + 1 $ < / span>.
Si vous calculez $ dp (i, 1) $ : valeur de $ DP (ch, 0, c) $ est $ DP (ch, 0, c) +1 $ ; Valeur de $ DP (ch, 1, c) $ est $ DP (ch, 1, c) + 1 $ < / span>.

Nous pouvons obtenir les matrices complètes $ dp (i, 0) $ et $ DP (i, 1) $ directement à partir des valeurs d'extrémité des sacs à dos (c'est-à-dire les valeurs de $ kn (dernier, j) $ pour tous $ j $ ). Le knapsack a $ o (\ # enfants * n) $ articles par nœud et fonctionne dans $ O (\ # enfants * n * n) $ par nœud. Par conséquent, la complexité totale de la solution est $ O (n ^ 3) $ . Veuillez noter que vous devrez modifier légèrement le knapack traditionnel 0-1 pour empêcher deux éléments qui représentent le même noeud d'être pris; Ce n'est pas très difficile. De plus, lors du calcul de la $ DP (I, 1) $ Array, veuillez noter que le nœud $ i $ lui-même est un nœud supplémentaire sur la couverture de sommet.

Je dois savoir s'il y a des solutions à temps plus rapidement que celui-ci, mais je n'en douterais pas.