transaction transaction transaction

transaction transaction transaction

【2017 ACM/ICPC Asia Regional Shenyang Online】

【DP问题】

Solution:

对于这个问题,首先可以想到一个暴力办法,即把每一种出发点到每一种结束点的可能性都枚举一遍,找到最优解,显然,这种办法虽然可以求出解,但是会超时,因此我们采用dp的办法来解决。我们建立一个二维dp数组,dp[i][0]表示从某个城市购买书籍并运送到这里的最少花费,存储为负值;dp[i][1]表示从某个城市送货到当前城市所能得到的最大收益。显然,dp[i][0] + dp[i][1]表示从某个城市出发经由城市i买到另外一所城市的最大收益,本题的最优解也就在这些值中产生。

#include <iostream>
#include <vector>

using namespace std;

struct node {
    int to, weight;
};

const int NIL = -1;
const int LIM = 1e5 + 10;

int val[LIM], n;
vector<node> edges[LIM];
int dp[LIM][2], ans = 0;

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

void init() {
    ans = 0;
    for (int i = 1; i <= n; i++) {
        edges[i].clear();
    }
}

void dfs(int crt, int from) {
    dp[crt][0] = -val[crt];
    dp[crt][1] = val[crt];
    for (vector<node>::iterator ite = edges[crt].begin(); ite != edges[crt].end(); ite++) {
        int to = ite->to;
        if (to == from) continue;
        dfs(to, crt);
        dp[crt][0] = maxi(dp[crt][0], dp[to][0] - ite->weight);
        dp[crt][1] = maxi(dp[crt][1], dp[to][1] - ite->weight);
    }
    ans = maxi(ans, dp[crt][0] + dp[crt][1]);
}

int main(void) {
    int t, from, to, w;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        init();
        for (int i = 1; i <= n; i++)
            scanf("%d", val + i);
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d", &from, &to, &w);
            edges[from].push_back({to, w});
            edges[to].push_back({from, w});
        }
        dfs(1, NIL);
        printf("%d\n", ans);
    }
    return 0;
}