将功补过
Case Time Limit:1000MS
Description
作为间谍专家的Elvis Han受窃取X星球军事中心的秘密情报,他已经成功进入军事中心。但是很不幸的是,在他还没有找到任务需要情报的时候就被发现,这时他清楚他不可能完成任务了,不过还有机会将功补过,也就是得到一些不如任务情报有价值的其他情报,如果得到的情报的总价值大于等于任务情报价值,他也不会受到惩罚。很幸运的是他已经得到的军事中心的地图,情报都是隐藏在各个道路上的,但是他只有时间遍历一定数量的路(时间宝贵呀!还要逃跑。。)现在你做为他的助手,给你地图和每个道路情报价值,希望你分析出,看他能不能将功补过。
军事中心是一个严格的二叉树,也就是说,如果有个点可以分道,一定是分出,也只分出2条道路,现在Elvis Han正处在第一个分道处,也就是说树的根结点处。每条道路上都有一个分数,就是这个道路上的情报价值。但是他只有时间走M条路,他的最终情报价值总和就是他所经过的路的情报价值总和(假设他到过的路一定可以把所有情报得到)希望你给出一个方案使得他可以尽量多地获取情报以便将功补过。
Input
共有N行:
第一行:3个数据:N,M,Q(N表示有多少个路口,包括分道和不分道的路口;M表示他可以有时间走的道路总数;Q表示他的任务情报的价值)
第2~N行:每行3个数据,Xi,Yi,Wi (X,Y表示第I条道路连接的2个路口,W表示这条道路上的情报价值分, 注意,所有数据均在Lonint范围内)
Output
共包含2行:
第一行:输出TRUE/FALSE(注意大小写),表示他是否可以收集够任务情报价值
第二行:输出一个数据:
如果他可以完成任务,就输出他收集的情报总价值超过任务情报价值的部分。(正数)
如果不能完成任务,就输出一个数,表示他不能还差多少分才够任务情报价值。(负数)
Sample Input
【样例输入1】
3 1 10
1 2 10
1 3 8
【样例输入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
Sample Output
【样例输出1】
TRUE
0
样例说明:(该部分不必输出)
3 2
(8)\ /(10)
1
(选择1条路当然选1-2)
【样例输出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,所以不可能完成任务)
Hint
<数据规模>
对于30%的数据 保证有N<=10
对于50%的数据 保证有N<=40
对于全部的数据 保证有 N<=100
解题思路
这题和P2015 二叉苹果树(树形dp)一样
只需要改一下输入,还有输出加一个特判就AC了
注意:输出要大写,不要写错了
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,q,m,b[1005],a[1005][1005],f[1005][1005],tree[1005][1005];
void build(int x)//建图
{
int o=0;//要在子程序int,不然会有问题
for(int i=0;i<=n;i++)//枚举每一个点
if(a[x][i]!=-1)//如果相连
{
o++;
b[i]=a[x][i];//i的根为a[x][i]
tree[x][o]=i;//树
a[x][i]=a[i][x]=-1;//清零
build(i);//递归
if(o==2)return;//退出
}
}
void dfs(int x,int k)//搜索
{
if(k==0)f[x][k]=0;//赋值
else if(tree[x][1]==0&&tree[x][2]==0)f[x][k]=b[x];
else
{
f[x][k]=0;
for(int i=0;i<k;i++)//枚举k
{
if(f[tree[x][1]][i]==0)dfs(tree[x][1],i);//搜索
if(f[tree[x][2]][k-i-1]==0)dfs(tree[x][2],k-i-1);
f[x][k]=max(f[x][k],(f[tree[x][1]][i]+f[tree[x][2]][k-i-1]+b[x]));//状态转移
}
}
}
int main()
{
scanf("%d%d%d",&n,&q,&m);
for(int i=0;i<=n;i++)//初值
for(int j=0;j<=n;j++)
a[i][j]=a[j][i]=-1;
for(int i=1;i<=n-1;i++)//输入
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x][y]=a[y][x]=z;
}
build(1);//建
dfs(1,q+1);//搜
if(f[1][q+1]<m)cout<<"false"<<endl;//特判再输出
else cout<<"true"<<endl;
cout<<f[1][q+1]-m;
}