UVALive 4015 树形dp

题目大意：

从一个根节点出发，走最多 x 的长度，问最多能走过多少个节点，图保证是一棵树

dp[0][i][j] , 表示走从i点为根的子树走过了j个点最后回到 i 最少需要多少时间
dp[1][i][j] , 同理，但表示不需要回到 i
那么由儿子不断向父亲更新，有4种情况

1.if(dp[0][u][k+j]<0 || dp[0][u][k+j]>dp[0][v][j]+dp[0][u][k]+2*e[i].d)
dp[0][u][k+j]=dp[0][v][j]+dp[0][u][k]+2*e[i].d;

2.if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[0][v][j]+dp[0][u][k]+e[i].d)
dp[1][u][k+j]=dp[0][v][j]+dp[0][u][k]+e[i].d;

3.if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[1][v][j]+dp[0][u][k]+e[i].d)
dp[1][u][k+j]=dp[1][v][j]+dp[0][u][k]+e[i].d;

4.if(dp[1][u][k+j]<0 || dp[1][u][k+j]>dp[0][v][j]+dp[1][u][k]+2*e[i].d)
dp[1][u][k+j]=dp[0][v][j]+dp[1][u][k]+2*e[i].d;

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 #define N 505

 #define ll long long

 ll dp[][N][N];

 int fa[N] , n , m;

 int first[N],k;

 struct Edge{

     int y , next , d;

     Edge(int y= , int next= , int d=):y(y),next(next),d(d){}

 }e[N<<];

 void add_edge(int x , int y , int d)

 {

     e[k] = Edge(y , first[x] , d);

     first[x] = k++;

 }

 void dfs(int u)

 {

     dp[][u][] = ;

     for(int i=first[u] ; ~i ; i=e[i].next){

         int v = e[i].y;

         dfs(v);

         for(int k=n ; k>= ; k--)

         {

             if(dp[][u][k]<) continue;

             for(int j= ; j<n ; j++){

                 if(dp[][v][j]<) continue;

                 if(dp[][u][k+j]< || dp[][u][k+j]>dp[][v][j]+dp[][u][k]+*e[i].d)

                     dp[][u][k+j]=dp[][v][j]+dp[][u][k]+*e[i].d;

                 if(dp[][u][k+j]< || dp[][u][k+j]>dp[][v][j]+dp[][u][k]+e[i].d)

                     dp[][u][k+j]=dp[][v][j]+dp[][u][k]+e[i].d;

                 if(dp[][v][j]<) continue;

                 if(dp[][u][k+j]< || dp[][u][k+j]>dp[][v][j]+dp[][u][k]+e[i].d)

                     dp[][u][k+j]=dp[][v][j]+dp[][u][k]+e[i].d;

             }

             if(dp[][u][k]<) continue;

             for(int j= ; j<=n ; j++){

                 if(dp[][v][j]<) continue;

                 if(dp[][u][k+j]< || dp[][u][k+j]>dp[][v][j]+dp[][u][k]+*e[i].d)

                     dp[][u][k+j]=dp[][v][j]+dp[][u][k]+*e[i].d;

             }

         }

     }

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("a.in" , "r" , stdin);

     #endif // ONLINE_JUDGE

     int cas = ;

     while(scanf("%d" , &n) , n)

     {

         printf("Case %d:\n" , ++cas);

         memset(first , - , sizeof(first));

         k = ;

         for(int i= ; i<=n ; i++) fa[i]=i;

         for(int i= ; i<n ; i++){

             int u,v,d;

             scanf("%d%d%d" , &u , &v , &d);

             u++ , v++;

             add_edge(v , u , d);

             fa[u] = v;

         }

         int st;

         for(int i= ; i<=n ; i++)

             if(fa[i]==i) st = i;

         memset(dp , - , sizeof(dp));

         dfs(st);

         /*debug

         for(int i=1 ; i<=n ; i++){

             for(int j=1 ; j<=n ; j++){

                 printf("%4I64d" , dp[1][i][j]);

             }

             cout<<endl;

         }*/

         scanf("%d" , &m);

         for(int i= ; i<m ; i++){

             int x;

             scanf("%d" , &x);

             int ret = ;

             for(int t= ; t<=n ; t++){

               //  cout<<dp[0][1][t]<<" "<<dp[1][1][t]<<endl;

                 if((dp[][st][t]<=x && dp[][st][t]>=) || (dp[][st][t]<=x && dp[][st][t]>=))

                     ret = max(ret , t);

             }

             printf("%d\n" , ret);

         }

     }

     return ;

 }

巴特西

UVALive 4015 树形dp

最新文章

热门文章