cobertura mínima de vértices para acceder a k bordes en un árbol
-
28-09-2020 - |
Pregunta
Necesito encontrar el número mínimo de $N$ vértices de un árbol con $N-1$ bordes, de modo que al menos $k$ Los bordes de ese árbol están conectados a estos vértices.
Por ejemplo, si $N=9$ y $K=6$ y tenemos este árbol:
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 respuesta correcta debería ser $\mathrm{min}=2$.
¿Alguna idea?
Solución
Hay un $\mathcal{O}(nk)$ Enfoque del DP.
Llamamos a una arista cubierta si seleccionamos un vértice al lado de ella.Arraigar el árbol en un vértice arbitrario. $r$.Definir $DP[i][b][t]$ como el número máximo de aristas en el subárbol del nodo $yo$ que se puede cubrir seleccionando como máximo $t$ nodos del subárbol.Si $b = 0$ no se nos permite seleccionar el nodo $yo$, y si $b = 1$ debemos seleccionarlo.
Si calculamos este DP, podemos resolver el problema, ya que el número mínimo de nodos a cubrir $k$los bordes son los más pequeños $t$ para cual $max(DP[r][0][t], DP[r][1][t]) \geq k$.Tenga en cuenta además que basta con calcular únicamente el $DP$ para $t\leqk$, como cualquier $ k < n $ Los nodos cubren al menos $k$ bordes.
Para dar la recurrencia para calcular el DP, primero damos la función de mochila:dejar $K(V_{1}, \puntos, V_{m})$ ser una matriz tal que
Begin {Ecation*} k (v_ {1}, dots, v_ {m}) [t] = max_ {t_ {1} + dots + t_ {m} = t} sum_ {j = 1} ^{m} v_ {j} [t_ {j}] end {ecuación*}
Tenga en cuenta que $K(K(V_{1}, \dots, V_{m-1}), V_{m}) = K(V_{1}, \dots, V_{m})$, y eso $K(A,B)$ se puede calcular directamente mediante la fórmula anterior en $\mathcal{O}(|A| \cdot |B|)$ tiempo.Por lo tanto calculando $K(V_{1}, \puntos, V_{m})$ acepta $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \sum_{j = 1}^{i-1} |V_{j}|)$ tiempo independientemente del orden en el que combinemos los conjuntos.Si sólo nos interesa el primero $k$ valores del DP, la complejidad cae a $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \min(k, \sum_{j = 1}^{i-1} |V_{j}|)) ps
Dejar $C_{i}$ ser el conjunto de hijos del nodo $yo$, y $C_{ij}$ ser el $j$º hijo de $yo$.Entoncesbegin {reunir*} 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 {reunir*}Dóndebegin {reunir*} 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 {recopilar*}Calcular la respuesta con esta recursividad requiere $\mathcal{O}(nk)$ tiempo.De manera informal, esto se debe a que en el transcurso del algoritmo, combinamos DP de un solo elemento en un DP que representa el árbol completo.lo hacemos como mucho $\frac{n}{k}$ combinaciones de conjuntos de tamaño $k$, y cualquier elemento nos cuesta como mucho $2k$ tiempo (si el elemento $x \en A$ nos cuesta $|B|$ tiempo al calcular $K(A,B)$) antes de fusionarse en un conjunto de tamaño $k$, por lo que la cantidad total de trabajo es como máximo $\mathcal{O}(k^{2} \frac{n}{k} + k n) = \mathcal{O}(nk)$.Esto es fácil pero tedioso de formalizar mediante inducción.
#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';
}
Otros consejos
Una solución simple es usar el estado $ dp (n, 2, n) $ . Deje que $ DP (I, 0, J) $ sea el número máximo de bordes que podemos obtener usando $ \ leq j $ nodos en el subtrete enraizado en el nodo $ i $ , con nodo $ i $ mismo No estar en la cubierta del vértice. Deje que $ DP (I, 1, J) $ sea el mismo, excepto el nodo $ i $ está incluido en la cubierta del vértice.
La transición en sí no es obvia, pero se puede hacer utilizando un método similar a la mochila. Considere a todos los niños del nodo $ i $ . Utilice todos los valores de $ dp (CH, 0, C) $ y $ dp (CH, 1, C) $ como elementos en dos mochilas separadas: una para calcular la matriz completa $ dp (I, 0) $ y uno para calcular la matriz completa $ DP (I, 1) $ . Los costos de los artículos son uniformemente $ C $ , mientras que los valores son los siguientes:
Si calcula $ dp (i, 0) $ : Valor de $ dp (CH, 0, C) $ es $ dp (CH, 0, C) $ ; Valor de $ dp (CH, 1, C) $ es $ dp (CH, 1, C) + 1 $ < / span>.
Si calcula $ DP (I, 1) $ : Valor de $ dp (CH, 0, C) $ es $ dp (CH, 0, C) +1 $ ; Valor de $ dp (CH, 1, C) $ es $ dp (CH, 1, C) + 1 $ < / span>.
Podemos obtener las matrices completas $ dp (I, 0) $ y $ dp (I, 1) $ directamente desde los valores de extremo de las mochilas (es decir, los valores de $ kn (ultimo, j) $ para todos $ j $ ). La mochila tiene $ o (\ # niños * n) $ artículos por nodo, y se ejecuta en $ o (\ # niños * n * n) $ por nodo. Por lo tanto, la complejidad total de la solución es $ o (n ^ 3) $ . Tenga en cuenta que tendrá que modificar ligeramente la mochila de 0-1 tradicional para evitar que se tomen los mismos artículos que representen el mismo nodo; Esto no es muy difícil. Además, al calcular el $ dp (i, 1) $ matriz, tenga en cuenta que el nodo $ i $ En sí mismo es un nodo extra en la cubierta del vértice.
Estoy seguro de que, si hay soluciones que se ejecutan en tiempo más rápido que este, pero no lo dudaría.