题意:给定一个图,无向,每条路有时间花费,每个地点有一个value;

求在给定的时间内得到的最大value

输入:

n:顶点数

ui  vi  ti :第i条路的起点,终点,时间

k m:开始点 给定时间

输出:

最大value

 

据说是树形dp!

树形dp?啥玩意儿?

反正我自己做出来了!

嗯,如果是树形dp的话,也做个纪念吧!

废话不多了,下面是我的代码:
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#define max(a,b) (a>b?a:b)
#define MAX 105
int main(){
int n;
while(scanf(“%d”,&n)==1){
int i,m,k,t,j,res=0;
int rank[MAX]={0},f[MAX]={0};
int dp[MAX][MAX+MAX]={0};
int map[MAX][MAX]={0};
memset(dp,0xf0,sizeof(dp));
for(i=1;i<=n;i++)                     //输入部分,没啥好说的!
scanf(“%d”,&dp[i][0]);
for(i=1;i<n;i++){
int s,e,t;
scanf(“%d%d%d”,&s,&e,&t);
map[s][e]=t;
map[e][s]=t;
}
scanf(“%d%d”,&k,&m);
rank[0]=k;
for(i=t=0;i<n;i++)              //建树,f[i]存父节点,rank[i]存子节点
for(j=1;j<=n;j++)
if(map[rank[i]][j]){
map[j][rank[i]]=0;
rank[++t]=j;
f[t]=rank[i];
}
for(i=n-1;i>=1;i–){                //dp过程,合并子节点到父节点,代码重点!
int ch=rank[i],j=f[i],mm=map[j][ch];
for(t=m/2;t>=mm;t–)
for(k=0;k<=t-mm;k++)
dp[j][t]=max(dp[j][t],dp[ch][t-mm-k]+dp[j][k]);
}
for(i=0;2*i<=m;i++)
res=max(dp[rank[0]][i],res);               //找答案,合并到上一部分也可以,这个不重要!
printf(“%d\n”,res);
}
return 0;
}

 

话说,我怎么也优化不到0ms啊,到底那些大牛是怎么做到的!艳羡!!!

发表评论

电子邮件地址不会被公开。

Post Navigation