HDU - 6201 transaction transaction transaction(树形dp)

transaction transaction transaction

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 2964 Accepted Submission(s): 1328

Problem Description

Kelukin is a businessman. Every day, he travels around cities to do some business. On August 17th, in memory of a great man, citizens will read a book named "the Man Who Changed China". Of course, Kelukin wouldn't miss this chance to make money, but he doesn't have this book. So he has to choose two city to buy and sell.
As we know, the price of this book was different in each city. It is ai yuan in i t city. Kelukin will take taxi, whose price is 1 yuan per km and this fare cannot be ignored.
There are n−1 roads connecting n cities. Kelukin can choose any city to start his travel. He want to know the maximum money he can get.

Input

The first line contains an integer T (1≤T≤10 ) , the number of test cases.
For each test case:
first line contains an integer n (2≤n≤100000 ) means the number of cities;
second line contains n numbers, the i th number means the prices in i th city; (1≤Price≤10000)
then follows n−1 lines, each contains three numbers x , y and z which means there exists a road between x and y , the distance is z km (1≤z≤1000) .

Output

For each test case, output a single number in a line: the maximum money he can get.

Sample Input

1 4 10 40 15 30 1 2 30 1 3 2 3 4 10

Sample Output

Source

2017 ACM/ICPC Asia Regional Shenyang Online

Recommend

liuyiding

每个城市都有种个价格，走每条路都要花费一种价格，问在哪里买一本书再卖到那里去能使得利益最大化。

我用dp[u][0]来表示从已遍历的某个点买书再走到到这里的最小的花费是多少（负数），用dp[u][1]来表示从已遍历的某个点卖书前走到到这里得到的最大利益是多少。然后每个点进行一次比较并更新ans值就好了。不过这样做需要注意的一个地方就是在便利到最后一个点的时候。。我们需要额外进行一次更新，就是对dp[u][0]+dp[u][1]与ans的更新就好了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int dp[maxn][3], val[maxn], head[maxn];//dp[][0]是买,dp[][1]是卖
int ans = 0;
struct *** {
	int v, w, ne;
}ed[maxn << 1];
int n, m, cnt;
void add(int u,int v,int w) {
	ed[cnt].v = v; ed[cnt].w = w;
	ed[cnt].ne = head[u]; head[u] = cnt++;
}
void init() {
	memset(head, -1, sizeof head);
	cnt = ans = 0;
	memset(dp, 0, sizeof dp);
}
void dfs(int u,int fa) {//dp[][0]是买后走到,dp[][1]是卖前走到
	int cost = -val[u], get = val[u];
	for (int i = head[u]; ~i; i = ed[i].ne) {
		int v = ed[i].v;
		if (v == fa)continue;
		dfs(v, u);
		cost = max(dp[v][0] - ed[i].w, cost);
		get = max(dp[v][1] - ed[i].w, get);
	}
	ans = max(cost + val[u], ans);
	ans = max(get - val[u], ans);
	dp[u][0] = cost;
	dp[u][1] = get;
//	cout << u << " : " << cost << " " << get << endl;
}
int main() {
	int te;
	scanf("%d", &te);
	while (te--) {
		init();
		scanf("%d", &n);
		for (int s = 1; s <= n; s++) scanf("%d", &val[s]);
		for (int i = 1; i < n; i++) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c); add(b, a, c);
		}
		dfs(1,0);
		ans = max(ans, dp[1][0] + dp[1][1]);;
		printf("%d\n", ans);
	}
}