学步园

这题看了点别人的思路。

先是用一次广搜，搜出从1到N的最短路径，判断是否小于T（就是判断下能否逃出去），然后将这条路径上的所有边的权值变成0，这样再进行一次树形DP那么刚刚为0的边一定会选进去，其他的边用DP选。有一点要注意，这时候权值要乘以2，因为要回来。不懂的话，画下图就知道了。

AC代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef struct{
	int to;
	int next;
	int length;
}Edge;

typedef struct{
	vector<int> edge;
	int time;
	int now;
}Node;

Edge edge[202];
int head[101];
int N, T;
int value[101];
int tot;
int dp[101][501];
bool visit[101];
int sum;

inline int max( int a, int b ){
	return ( a > b ? a : b );
}

void add_edge( int a, int b, int c ){
	edge[tot].to = b;
	edge[tot].length = c;
	edge[tot].next = head[a];
	head[a] = tot++;
	edge[tot].to = a;
	edge[tot].length = c;
	edge[tot].next = head[b];
	head[b] = tot++;
}

void BFS(){
	bool mark[101];
	queue<Node> q;
	
	Node start;
	Node end;
	start.now = 1;
	start.time = 0;
	start.edge.clear();
	q.push( start );

	memset( mark, false, sizeof( mark ) );
	mark[1] = true;

	while( !q.empty() ){
		Node n = q.front();
		q.pop();

		if( n.now == N ){
			end = n;
			break;
		}

		int t = n.now;
		for( int i = head[t]; i != -1; i = edge[i].next ){
			Node temp = n;
			temp.now = edge[i].to;
			temp.edge.push_back( i );
			temp.time += edge[i].length;
			if( mark[temp.now] ){
				continue;
			}
			mark[temp.now] = true;
			q.push( temp );
		}
	}

	sum = 0;
	for( int i = 0; i < end.edge.size(); i++ ){
		sum += edge[end.edge[i]].length;
		edge[end.edge[i]].length = 0;
	}
}

void DFS( int n, int pre ){
	if( head[n] == -1 || ( edge[head[n]].to == pre && edge[head[n]].next == -1 ) ){
		for( int i = 0; i <= T; i++ ){
			dp[n][i] = value[n];
		}
		return;
	}

	for( int i = head[n]; i != -1; i = edge[i].next ){
		int t = edge[i].to;
		if( visit[t] ){
			continue;
		}
		if( t == pre ){
			continue;
		}
		visit[t] = true;
		DFS( t, n );
		for( int j = T; j >= 0; j-- ){
			for( int k = 0; k + 2 * edge[i].length <= j; k++ ){ 
				dp[n][j] = max( dp[n][j], dp[n][j-k-2*edge[i].length] + dp[t][k] );
			}
		}
	}
	for( int i = 0; i <= T; i++ ){
		dp[n][i] += value[n];
	}
}

int main(){
	while( scanf( "%d%d", &N, &T ) != EOF ){
		memset( value, 0, sizeof( value ) );
		memset( head, -1, sizeof( head ) );
		tot = 0;

		for( int i = 1; i < N; i++ ){
			int temp1, temp2, temp3;
			cin >> temp1 >> temp2 >> temp3;
			add_edge( temp1, temp2, temp3 );
		}
		for( int i = 1; i <= N; i++ ){
			cin >> value[i];
		}

		BFS();

		if( sum <= T ){
			memset( dp, 0, sizeof( dp ) );
			memset( visit, 0, sizeof( visit ) );
			DFS( 1, 0 );
			cout << dp[1][T-sum] << endl;
		}else{
			cout << "Human beings die in pursuit of wealth, and birds die in pursuit of food!" << endl;
		}
	}
	return 0;
}