题目链接:
UVALive 7003 A Balance Game on Trees
题意:
给一个 n 个节点和每个节点的儿子的有根树,根为1,初始时树上每个节点的颜色都为白色,现在要将树上的一些节点的颜色染为黑色使得每个白色节点的周围(直接相连的边的另一端)恰好有
数据范围: n≤100,K≤10
分析:
每个节点的颜色无非两种:黑色和白色。我们用 black[u] 和 white[u] 表示当 u 分别是黑色和白色时,以
从根节点
black[u] 的状态转移:
对于 u 的每一个儿子v ,如果 v 的儿子数量大于等于K?1 ,那么如果选择 v 的颜色为白色(记此时的答案为son ),可以得到的最优解是: son=white[v][K?1]+1 ,否则 v 节点就不能染为白色(因为v 节点的周围不能凑够 K 个黑色节点),也就是son=0 。
black[u]+=max(black[v],son)white[u][] 的状态转移:
这时对于 u 从它的每个儿子v 的状态转移只能 v 是黑色或者white[v][K] 。
考虑 white[u][i] 的情况,这里需要 u 的所有儿子中有i 个是黑色,其余的是白色。如何求这个最优解呢?如果暴力枚举的话,最坏的时间复杂度是: O(2n) !o(╯□╰)o
我们先把所有儿子全是白色的情况相加记为 sum :
sum=∑white[v][K]
再把每个儿子选择黑色和白色的最优解差值记为 diff[] :
diff[i]=black[v]?white[v][K]
因为必须有 i 个儿子是黑色,那么我们选择的这i 个儿子必然是 diff 值最大的前 i 个!详情看代码~最坏的时间复杂度是:
O(n2logn?K) ,实际运行是应远小于这个复杂度。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
const int MAX_N = 110;int T, n, K, sum;
int white[MAX_N][15], black[MAX_N], vis[MAX_N], diff[MAX_N];
vector<int> vec[MAX_N];void dfs_son(int u, int p)
{int size = vec[u].size();for (int i = 0; i < size; ++i) {int v = vec[u][i];dfs_son(v, u);}sum = 0;for (int i = 0; i < size; ++i) {int v = vec[u][i];int son = 0;if (vec[v].size() >= K - 1) son = white[v][K - 1] + 1;black[u] += max(son, black[v]);son = white[v][K];sum += son;diff[i] = black[v] - son;}sort(diff, diff + size);for (int i = 1; i <= K; ++i) {if (i > size) break;white[u][i] = sum;for (int j = size - 1; j >= size - i; --j) {white[u][i] += diff[j];}}if (size >= K) white[u][K]++;
}int main()
{scanf("%d", &T);while (T--) {scanf("%d%d", &n, &K);for (int i = 1; i <= n; ++i) { vec[i].clear(); }memset(black, 0, sizeof(black));memset(white, 0, sizeof(white));getchar();for (int i = 1, j; i <= n; ++i) {while (1) {scanf("%d", &j);if (j == 0) break;vec[i].push_back(j);if (getchar() == '\n') break;}}dfs_son(1, 0);printf("%d\n", max(black[1], white[1][K]));}return 0;
}