poj 2152 Fire

一道我觉得很难的树形dp，想了很久都想不出状态转移方程式，搜了题解之后也看了很久。

思路：用dp[u][i]表示以u为根的子树满足条件，并且结点u依赖于结点i的最小花费。

　　用best[u]表示以u根的子树满足条件的最小花费，那么best[u]=min(dp[u][i])。

　　求best[u]时，先跑一遍dfs得到所有结点距离u的距离dis[i]。如果dis[i]>d[u]，那么u没法依赖i，此时dp[u][i]=inf。否则dis[i]<=d[u]，此时dp[u][i]=w[i]+sum( min( best[v] , dp[v][i]-w[i] ) )，其中i从1遍历到n，v是u的子结点。因为v的依赖有两种情况，如果v依赖于以v为根的子树中的结点，即best[v]; 如果v依赖于其余的结点，那么一定是i。反证一下，如果v依赖于k，那么u也一定依赖于k。所以应取best[v]和dp[v][i]-w[i]的最小值，减w[i]是因为w[i]多加了一次。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map> 
#include <stack>
#include <sstream>
#include <set>
#pragma GCC optimize(2)

//#define int long long
#define mm(i,v) memset(i,v,sizeof i);
#define mp(a, b) make_pair(a, b)
#define pi acos(-1)
#define fi first
#define se second
//你冷静一点，确认思路再敲！！！ 

using namespace std;
typedef long long ll;
typedef pair<int, int > PII;
priority_queue< PII, vector<PII>, greater<PII> > que;
stringstream ssin; //  ssin << string   while ( ssin >> int)

const int N = 2e3 + 5, mod = 1e9 + 9, INF = 0x3f3f3f3f;
int T, n, m, cnt, wei[N], d[N], dp[N][N], dis[N], idx;
int e[N], h[N], ne[N], w[N], best[N];

inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void init() {
    mm(h, -1);
    idx = 0;
    cnt = 0;
}

void getdis(int u, int fa, int len) {
    dis[u] = len;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i], z = w[i];
        if (v == fa) continue;
        getdis(v, u, len + z);
    }
}

void dfs(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        dfs(v, u);
    }
    getdis(u, -1, 0);
    best[u] = INF;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] > d[u]) dp[u][i] = INF;
        else {
            dp[u][i] = wei[i];
            for (int j = h[u]; ~j; j = ne[j]) {
                int v = e[j];
                if (v == fa) continue;
                dp[u][i] += min(best[v], dp[v][i] - wei[i]);
            }
        }
        best[u] = min(best[u], dp[u][i]);
    }
}

int main()
{
    cin >> T;
    while (T--) {
        init();
        cin >> n;
        for (int i = 1; i <= n; ++i) wei[i] = read();
        for (int i = 1; i <= n; ++i) d[i] = read();
        for (int i = 1; i < n; ++i) {
            int a, b, c;
            a = read(); b = read(); c = read();
            add(a, b, c);
            add(b, a, c);
        }
        dfs(1, -1);
        cout << best[1] << endl;
    }
    // system("pause");
    return 0;
}

View Code