Min Vertex Cover pour accéder aux bords K dans un arbre
-
28-09-2020 - |
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?
La solution
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
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';
}
Autres conseils
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.