问题描述
Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。
请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。
Input
输入文件中数据表示一棵树，描述如下：
第一行 N，表示树中结点的数目。
第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，…，rk。
对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。
Output
输出文件仅包含一个数，为所求的最少的士兵数目。
Sample Input
4
0 1 1
1 2 2 3
2 0
3 0
Sample Output
1
算法分析
树型DP
首先建树，得到根结点。设置数组F[N][2]，f[x][1]表示要看守住以x为根的子树中所有边，x处有士兵时需要的最少士兵数，f[x][0] 表示要看守住以x为根的子树中所有边，x处无士兵时需要的最少士兵数。自下而上地计算每个结点的两种值：一个结点的有士兵的值等于它所有子树的有士兵的值与没有士兵的值的较小值之和再加1；一个结点没有士兵的值等于它所有子树的有士兵的值之和。根结点有士兵的值和没有士兵的值中的较小值即为答案。
【代码】
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 55 56 57 | #include <stdio.h> #include <string.h> #define min(a,b) a<b?a:b typedef struct { int num; int child[1501]; }node; //树型结构 node a[1501]; int f[1501][2]; int n; void dp(int root) { int i; if (a[root].num == 0) { f[root][1] = 1; f[root][0] = 0; return; } f[root][1] = 1; f[root][0] = 0; for (i = 0; i < a[root].num; i++) { dp(a[root].child[i]); //先dp再相加 从下往上 f[root][1] += min(f[a[root].child[i]][1], f[a[root].child[i]][0]); f[root][0] += f[a[root].child[i]][1]; } } int main() { int i, j, k, r, root; scanf("%d", &n); r = 0; root = 0; for (i = 0; i < n; i++) { scanf("%d", &k); r += k; scanf("%d", &a[k].num); for (j = 0; j < a[k].num; j++) { scanf("%d", &a[k].child[j]); root += a[k].child[j]; } } root = r - root; //求根结点 memset(f, 0, sizeof(f)); dp(root); printf("%d\n", min(f[root][1], f[root][0])); return 0; } |