树形DP 将功补过

Published on 2009 / 08 / 04

这几天做了一些树形DP的题，感觉不错！

将功补过（inform.pas/c/cpp）

【问题背景】

作为间谍专家的Elvis Han受窃取X星球军事中心的秘密情报，他已经成功进入军事中心。但是很不幸的是，在他还没有找到任务需要情报的时候就被发现，这时他清楚他不可能完成任务了，不过还有机会将功补过，也就是得到一些不如任务情报有价值的其他情报，如果得到的情报的总价值大于等于任务情报价值，他也不会受到惩罚。很幸运的是他已经得到的军事中心的地图，情报都是隐藏在各个道路上的，但是他只有时间遍历一定数量的路（时间宝贵呀！还要逃跑。。）现在你做为他的助手，给你地图和每个道路情报价值，希望你分析出，看他能不能将功补过。

【问题描述】

军事中心是一个严格的二叉树，也就是说，如果有个点可以分道，一定是分出，也只分出2条道路，现在Elvis Han正处在第一个分道处，也就是说树的根结点处。每条道路上都有一个分数，就是这个道路上的情报价值。但是他只有时间走M条路，他的最终情报价值总和就是他所经过的路的情报价值总和（假设他到过的路一定可以把所有情报得到）希望你给出一个方案使得他可以尽量多地获取情报以便将功补过。

【输入格式】

在输入文件inform.in中，共有N行：

第一行：3个数据：N，M，Q（N表示有多少个路口，包括分道和不分道的路口；M表示他可以有时间走的道路总数；Q表示他的任务情报的价值）

第2~N行：每行3个数据，Xi,Yi,Wi (X，Y表示第I条道路连接的2个路口，W表示这条道路上的情报价值分, 注意，所有数据均在Lonint范围内)

【输出格式】

在输出文件inform.out中，共包含2行：

第一行：输出TRUE/FALSE（注意大小写），表示他是否可以收集够任务情报价值

第二行：输出一个数据：

如果他可以完成任务，就输出他收集的情报总价值超过任务情报价值的部分。（正数）
如果不能完成任务，就输出一个数，表示他不能还差多少分才够任务情报价值。（负数）

【输入样例1】

3 1 10
1 2 10
1 3 8

【输出样例1】

TRUE
0

样例说明：(该部分不必输出)
3 2
（8）\ /（10）
1 （选择1条路当然选1-2）

【输入样例2】

9 3 49
6 2 15
7 2 10
8 7 6
7 9 15
1 3 20
2 1 10
4 3 8
3 5 7

【输出样例2】

FALSE
-4

样例说明：
8 9
(6) \ / (15)
6 7 4 5
（15）\ / （10）\ （8） /（7）
2 3
（10）\ /（20）
1(由于他最大可以取得的是[1->3]+[1->2]+[2->6]3条路径的价值，才45，所以不可能完成任务)

【数据规模】

对于30%的数据保证有N<=10
对于50%的数据保证有N<=40
对于全部的数据保证有 N<=100

我的程序

#include<stdio.h>

FILE *fs, *fp;
long Max, N, M, Q, Map[101][101], Re[101][101];
struct {
    int fa;
    int lc;
    int rc;
} Tree[101];

void Make_tree(int site, int father) {
    int a;
    Tree[site].fa = father;
    for (a = 1; a <= N; a++)
        if (Map[site][a] != 0 && a != father) {
            Tree[site].lc = a;
            Make_tree(a, site);
            a++;
            break;
        }
    for (; a <= N; a++)
        if (Map[site][a] != 0 && a != father) {
            Tree[site].rc = a;
            Make_tree(a, site);
            a++;
            break;
        }
}

long Dp(int site, long time) {
    if (time == 0)
        return 0;
    else if (Re[site][time] != 0)
        return Re[site][time];
    else if (Tree[site].lc == 0 && Tree[site].rc == 0)
        return 0;
    else {
        long a, b;
        if (Tree[site].lc != 0) {
            a = Dp(Tree[site].lc, time - 1);
            a += Map[site][Tree[site].lc];
            Re[site][time] = a > Re[site][time] ? a : Re[site][time];
        }
        if (Tree[site].rc != 0) {
            a = Dp(Tree[site].rc, time - 1);
            a += Map[site][Tree[site].rc];
            Re[site][time] = a > Re[site][time] ? a : Re[site][time];
        }
        if (Tree[site].rc != 0 && Tree[site].lc != 0) {
            for (b = 0; b <= time - 2; b++) {
                a = Dp(Tree[site].lc, b);
                a += Map[site][Tree[site].lc];
                a += Dp(Tree[site].rc, time - 2 - b);
                a += Map[site][Tree[site].rc];
                Re[site][time] = a > Re[site][time] ? a : Re[site][time];
            }
        }
        return Re[site][time];
    }
}

int main() {
    fs = fopen("inform.in", "r");
    fp = fopen("inform.out", "w");
    fscanf(fs, "%ld %ld %ld", &N, &M, &Q);
    long a, b, c;
    for (a = 1; a < N; a++) {
        fscanf(fs, "%ld %ld", &b, &c);
        fscanf(fs, "%ld", &Map[c]);
        Map[c] = Map[c];
    }
    Make_tree(1, 0);
    Max = Dp(1, M);
    if (Max >= Q)
        fprintf(fp, "TRUE\n%ld\n", Max - Q);
    else
        fprintf(fp, "FALSE\n%ld\n", Max - Q);
    fclose(fs);
    fclose(fp);
    return 0;
}