cobertura mínima de vértices para acessar k arestas em uma árvore
-
28-09-2020 - |
Pergunta
Eu preciso encontrar o número mínimo de $N$ vértices em uma árvore com $N-1$ bordas, de modo que pelo menos $K$ arestas dessa árvore estão conectadas a esses vértices.
Por exemplo, se $N=9$ e $K=6$ e temos esta árvore:
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
A resposta certa deveria ser $\matrm{min}=2$.
Alguma ideia?
Solução
Existe um $\mathcal{O}(nk)$ Abordagem DP.
Chame uma aresta coberta se selecionarmos um vértice próximo a ela.Enraíze a árvore em um vértice arbitrário $r$.Definir $DP[i][b][t]$ como o número máximo de arestas na subárvore do nó $i$ que pode ser coberto selecionando no máximo $t$ nós da subárvore.Se $b = 0$ não temos permissão para selecionar o nó $i$, e se $b = 1$ devemos selecioná-lo.
Se calcularmos este DP, podemos resolver o problema, pois o número mínimo de nós para cobrir $k$as bordas são as menores $t$ para qual $max(DP[r][0][t], DP[r][1][t]) \geq k$.Observe ainda que basta apenas calcular o $DP$ para $t \leq k$, como qualquer $k<n$ nós cobrem pelo menos $k$ arestas.
Para fornecer a recorrência para calcular o DP, primeiro fornecemos a função mochila:deixar $K(V_{1}, \pontos, V_{m})$ seja uma matriz tal que
\begin{equação*} K(V_{1}, \dots, V_{m})[t] = \max_{t_{1} + \dots + t_{m} = t} \sum_{j = 1}^{m} V_{j}[t_{j}] \end{equação*}
Observe que $K(K(V_{1}, \dots, V_{m-1}), V_{m}) = K(V_{1}, \dots, V_{m})$, e essa $K(A,B)$ pode ser calculado diretamente pela fórmula acima em $\mathcal{O}(|A| \cdot |B|)$ tempo.Portanto, calculando $K(V_{1}, \pontos, V_{m})$ leva $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \sum_{j = 1}^{i-1} |V_{j}|)$ tempo, independentemente da ordem em que combinamos os conjuntos.Se estivermos interessados apenas no primeiro $k$ valores do DP, a complexidade cai para $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \min(k, \sum_{j = 1}^{i-1} |V_{j}|)) $
Deixar $C_{i}$ seja o conjunto de filhos do nó $i$, e $C_{ij}$ seja o $j$o filho de $i$.Então\begin{reunir*} DP[i][0][t] = K(V_{1}, \pontos, V_{|C_{i}|}) [t]\\ DP[i][1][t] = |C_{i}| + K(V'_{1}, \pontos, V'_{|C_{i}|}) [t-1] \end{reunir*}Onde\begin{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{reunir*}Calcular a resposta com esta recursão leva $\mathcal{O}(nk)$ tempo.Informalmente, isso ocorre porque, ao longo do algoritmo, combinamos DPs de elemento único em um DP que representa a árvore inteira.Fazemos no máximo $\frac{n}{k}$ combinações de conjuntos de tamanho $k$, e qualquer elemento nos custa no máximo US$ 2 mil$ tempo (se elemento $x\em A$ nos custa $|B|$ tempo ao calcular $K(A,B)$) antes de ser mesclado em um conjunto de tamanho $k$, então a quantidade total de trabalho é no máximo $\mathcal{O}(k^{2} \frac{n}{k} + k n) = \mathcal{O}(nk)$.Isso é fácil, mas tedioso de formalizar com indução.
#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';
}
Outras dicas
Uma solução simples é usar o estado $dp(n,2,n)$.Deixar $dp(i,0,j)$ seja o número máximo de arestas que podemos obter usando $\leq j$ nós na subárvore com raiz no nó $i$, com nó $i$ em si não está na cobertura do vértice.Deixar $dp(i,1,j)$ ser o mesmo, exceto o nó $i$ está incluído na cobertura do vértice.
A transição em si não é óbvia, mas pode ser feita usando um método semelhante ao da mochila.Considere todos os filhos do nó $i$.Use todos os valores de $dp(ch,0,c)$ e $dp(ch,1,c)$ como itens em duas mochilas separadas:um para calcular o array completo $dp(i,0)$ e um para calcular o array completo $dp(i,1)$.Os custos dos itens são uniformemente $c$, enquanto os valores são os seguintes:
Se calcular $dp(i,0)$:valor de $dp(ch,0,c)$ é $dp(ch,0,c)$;valor de $dp(ch,1,c)$ é $dp(ch,1,c)+1$.
Se calcular $dp(i,1)$:valor de $dp(ch,0,c)$ é $dp(ch,0,c)+1$;valor de $dp(ch,1,c)$ é $dp(ch,1,c)+1$.
Podemos obter os arrays completos $dp(i,0)$ e $dp(i,1)$ diretamente dos valores finais das Mochilas (ou seja, os valores de $kn(último,j)$ para todos $j$).A mochila tem $O(\#filhos *n)$ itens por nó e é executado em $O(\#filhos * n * n)$ por nó.Portanto, a complexidade total da solução é $O(n^3)$.Observe que você terá que modificar ligeiramente a mochila 0-1 tradicional para evitar que dois itens que representem o mesmo nó sejam levados;isso não é muito difícil.Além disso, ao calcular o $dp(i,1)$ array, observe que o nó $i$ em si é um nó extra na cobertura do vértice.
Tenho certeza de que existem soluções rodando mais rápido que esta, mas não duvido.