木の中のkエッジにアクセスするための最小頂点カバー
-
28-09-2020 - |
質問
$ n-1 $ << $ n $ visticesの最小数を見つける必要があります。/ SPAN>エッジ、それで、少なくとも $ k $ そのツリーのエッジがこれらの頂点に接続されています。
例えば、 $ n= 9 $ と $ 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
.
右回答は $ \ mathrm {min}= 2 $ です。
あらゆる考え?
解決
$ \ mathcal {o}(nk)$ dpアプローチです。
エッジを呼び出してください。その隣の頂点を選択した場合は、エッジを呼び出します。任意の頂点 $ r $ でツリーをルートします。 $ dp [i] [b] $ ノード $ iのサブツリーの最大エッジ数として。サブツリーから $ t $ ノードを選択してカバーすることができます。 $ b= 0 $ の場合、ノード $ i $ 、および $ b= 1 $ それを選択する必要があります。
このDPを計算すると、 $ k $ エッジが最小の $ t $ $ max(dp [r] [0] [t]、dp [r] [1] [t])\ geq k $ 。さらに、 $ dp $ のみを計算するだけで十分です。 $ k
DPを計算するための再発を与えるために、まずナップザック機能を与えます。 $ k(v_ {1}、\ dots、v_ {m})$
のような配列になる\ begin {方程式*} k(v_ {1}、\ dots、v_ {m})[t]=max_ {t_ {1} + \ dots + t_ {m}= t} \ sum_ {j= 1} ^ {m} v_ { j} [T_ {j}] \ end {方程式*}
$ k(k(v_ {1}、\ dots、v_ {m-1})、v_ {m})= k(v_ {1}、\ドット、V_ {M})$ 、およびその $ k(a、b)$ は、 $ \ mathcal {O}(| a | \ Cdot | b |)$ 時間。したがって、 $ k(v_ {1}、\ dots、v_ {m})$ を受け取ります $ \ mathcal {O} (\ sum_ {i= 2} ^ {m} | \ {i} | \ sum_ {j= 1} ^ {i-1} | v_ {j} |)$ {j} | $ use順序に関係なくセット内の $ k $ 値のみに関心がある場合、複雑さは $ \ \ \ \ \ \ mathcal {o}(\ sum_ {i= 2} ^ {m} | v_ {i} | \ min(k、\ sum_ {j= 1} ^ {i-1} | V_ {j} |)$ < / SPAN>
$ c_ {i} $ ノード $ i $ の子のセットです。 $ c_ {ij} $ $ j $ " $ i $ 。それから \ begin {Gaygh *} 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 {Galy *} どこ \ begin {Gaygh *} V_ {j} [t]=max(dp [c_ {ij}] [0]、dp [c_ {ij}] [1] [t] + 1)\\ v '_ {j} [t]=max(dp [c_ {ij}] [t]、dp [c_ {ij}] [1] [t])\\ \ end {Galy *} この再帰による回答を計算すると、 $ \ mathcal {o}(nk)$ 時間がかかります。非公式にこれは、アルゴリズムの過程で、単一要素DPSを木全体を表すDPに結合するためです。 $ \ frac {n} {k} $ {span class="math-container"> $ k $ の組み合わせの組み合わせまた、任意の要素は $ 2K $ 時間($ $ x \ x \ x \ x \ x \ x \ x \ \ x \ \ x \ x \ x})米国 $ | B | $ $ k(a、b)$ )を計算する前にサイズのセット $ k $ のセットになるので、合計作業量は $ \ mathcal {o}(k ^ {2} \ frac {n} {k} + kn)=mathcal {o}(nk)$ 。これは簡単ですが、誘導で形式化するのは面倒です。
#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';
}
. 他のヒント
簡単な解決策は、状態 $ dp(n、2、n)$ を使用することです。 $ dp(i,0、j)$ $ \ leq jを使用して得ることができるエッジの最大数です。ノード $ i $ 、ノード $ i $ それ自体を求めて、サブツリーのノード。頂点カバーに入っていない。 $ dp(i,1、j)$ を同じにすると、ノード $ i $ が含まれています頂点カバーに。
遷移自体は明らかではありませんが、ナップザックのような方法で行うことができます。ノード $ i $ のすべての子供を検討してください。 $ dp(ch、0、c)$ と $ dp(ch、1、c)$のすべての値を使用してください。 2つの別々のナップザックの項目として:全配列 $ dp(i,0)$ を計算するためのもの、およびフル配列 $ DP(I、1)$ 。アイテムのコストは、一様に $ c $ ですが、値は次のとおりです。
$ dp(i,0)$ : $ dp(ch、0、c)$の値は $ dp(ch、0、c)$ です。 $ dp(ch、1、c)$ の値は $ dp(ch、1、c)+ 1 $ < /スパン>。
$ dp(i,1)$ を計算する場合は、 $ dp(ch、0、c)$ は $ dp(ch、0、c)+1 $ です。 $ dp(ch、1、c)$ の値は $ dp(ch、1、c)+ 1 $ < /スパン>
フルアレイ $ DP(I、0)$ 、 $ dp(i,1)$ ナップザックの終了値から直接(つまり、 $ kn(last、j)$ の値 "math-の値コンテナ "> $ J $ )。 NAPSACKは、 $ O(\#chiliter * n)$ 項目ごとに $ O(\#の子供たち)で実行されています。 * n * n)$ はノードごとに。したがって、ソリューションの合計複雑度は $ O(n ^ 3)$ です。同じノードが取られることを表す2つの項目を防ぐために、従来の0-1ナップザックを少し変更する必要があることに注意してください。これはあまり難しくありません。また、 $ dp(i,1)$ 配列を計算するときは、ノード $ i $ それ自体は頂点カバーの余分なノードです。
この1より速く時間内に稼働している場合は必ず注意していますが、それを疑いません。