給一棵$N$個節點的樹，將最少點塗色，使得每個沒被塗色的點都至少跟一個塗色的點相鄰。
$N\le 10000$
這題有個專有名詞叫樹上最少獨立集。
可以考慮dp，令dp[i]
[0]: 該點塗色。
[1]: 該點不塗色，且子節點至少有一個有塗色。
[2]: 該點不塗色，且子節點也都不塗。
令節點1為根，答案就會是min(dp[1][0], dp[1][1])，dp[1][2]為不符合要求的，所以不能當答案。
接著是轉移，令v為i的所有子節點
$$dp[i][0]=1+\sum \min^2_{x=0}dp[v][x]$$
$$dp[i][2]=\sum dp[v][1]$$
剩下1的轉移，理想情況下
$$dp[i][1]=\sum min(dp[v][1], dp[v][0])$$
然而要考慮dp[v][0]的轉移數量，如果全部的轉移來源都是dp[v][1]，那就得使其中一個變成dp[v][0]，詳細看code(#
時間複雜度$\mathcal{O}(N)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
const int INF = 0x3F3F3F3F;
signed main() { EmiliaMyWife
int n;
while(cin >> n) {
vector<vector<int>> edge(n + 1);
vector<array<ll, 3>> dp(n + 1);
for(int i = 1, a, b; i < n; i++) {
cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
const function<void(int, int)> dfs = [&] (int u, int p) {
dp[u][0] = 1;
ll res = INF, cnt = 0;
for(int v : edge[u]) {
if(v == p)
continue;
dfs(v, u);
dp[u][0] += *min_element(dp[v].begin(), dp[v].end());
dp[u][1] += dp[v][1];
dp[u][2] += dp[v][1];
if(dp[v][0] <= dp[v][1])
cnt++, dp[u][1] += dp[v][0] - dp[v][1];
else
res = min(res, dp[v][0] - dp[v][1]);
}
if(!cnt)
dp[u][1] += res;
};
dfs(1, 1);
cout << min(dp[1][0], dp[1][1]) << '\n';
}
}
|