本文共 1711 字，大约阅读时间需要 5 分钟。

1、

2、题目大意：

一个墓中有n个房间，各个房间有连通的路，走每一条路都要花费一定的时间，并且每个房间都有一定量的财富，现在这个墓将在m分钟之后倒塌，从1号房间出发，出口在n号房间，求是否能安全逃出，如果能安全逃出去，输出可以获得的最大价值是多少？

dp[i][j]表示以i为根，花费J分钟可以获得的最大价值

我们首先从1号点到n号点求一个最短路径，我们最终要的答案，最短路径走一遍，在这个基础上在去别的分支取财富，所以别的分支都是去取完再回到最短路上，所以需要花费2倍的时间

dfs_time()求出最短路花费的时间，如果这个时间比要求的时间还要长，也就是说不管怎么走都走不出去

如果能出去，那么我们再用dfs()更新各个顶点为根的值，

dp[u][j]=max(dp[u][j],dp[u][j-k-2*w[i]]+dp[v][k]);

3、AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 105int V[N*2],w[N*2],next[N*2],head[N*2];int tot,tim,n,m,num[N];int dp[N][505];void add_edge(int a,int b,int c){    V[tot]=b;    w[tot]=c;    next[tot]=head[a];    head[a]=tot++;}int dfs_time(int u,int fa){    if(u==n)    return 1;    for(int i=head[u];i!=-1;i=next[i])    {        int v=V[i];        if(v!=fa)        {            if(dfs_time(v,u))            {                tim+=w[i];                w[i]=0;                return 1;            }        }    }    return 0;}void dfs(int u,int fa){    for(int i=0;i<=m;i++)    dp[u][i]=num[u];    for(int i=head[u];i!=-1;i=next[i])    {        int v=V[i];        if(v!=fa)        {            dfs(v,u);            for(int j=m;j>=0;j--)            {                for(int k=0;k<=j-w[i]*2;k++)                {                    dp[u][j]=max(dp[u][j],dp[u][j-k-2*w[i]]+dp[v][k]);                }            }        }    }}int main(){    int a,b,c;    while(scanf("%d%d",&n,&m)!=EOF)    {        tot=0;        memset(head,-1,sizeof(head));        for(int i=1;i
      
       m)        printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");        else        {            m-=tim;            dfs(1,-1);            printf("%d\n",dp[1][m]);        }    }    return 0;}
      
     
    
   

转载地址：http://wgddi.baihongyu.com/