题目链接：http://poj.org/problem?id=2152
题目大意：给定n个节点组成的树，树有边权.现在要在一些点上建立消防站，每个点建站都有个cost[i]，如果不在当前的点上建站，也要依赖其他的消防站，并且距离不超过limit[i]。求符合上述条件的最小费用建站方案。n <= 1000.
解题思路：复杂度为O(n^2)的树形DP.因为要依赖其他站点，所以不仅仅只从子树中获取信息，也可能从父亲结点，兄弟结点获取信息，所以在计算每个点时首先想到要枚举，因为n特别小，允许我们枚举。设dp[i][j]表示i点及其子树都符合情况下i点依赖j点的最小花费，有了这个似乎还不够，再开个一维数组best，best[i]表示以i为根的子树符合题目要求的最小花费。这样状态转移方程就是dp[i][j]
= cost[j] + sum(min(dp[k][j]-cost[j],best[k])) (k为i的子节点，j为我们枚举的n个点)，因为i的每个子节点可以和i一样依赖j结点，那么花费是dp[k][j]-cost[j]，或者依赖以k为根的树中的某点，花费是best[k]，最后再加上cost[j]，因为要在j结点建站所以要增加花费。
你问我怎么想到的，我不会告诉你我看了陈启峰的论文。
测试数据：
5
5
1 1 1 1 1
1 1 1 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5
1 1 1 1 1
2 1 1 1 2
1 2 1
2 3 1
3 4 1
4 5 1
5
1 1 3 1 1
2 1 1 1 2
1 2 1
2 3 1
3 4 1
4 5 1
4
2 1 1 1
3 4 3 2
1 2 3
1 3 3
1 4 2
4
4 1 1 1
3 4 3 2
1 2 3
1 3 3
1 4 2
代码：
- #include <stdio.h>
- #include <vector>
- #include <string.h>
- using namespace std;
- #define MAX 1100
- #define INF 2147483647
- #define min(a,b) (a)<(b)?(a):(b)
- #define max(a,b) (a)>(b)?(a):(b)
- struct node {
- int v,len;
- }now;
- vector<node> tree[MAX];
- int n,cur,best[MAX],dp[MAX][MAX]; //best[i]表示以i为根的子树的最小花费，dp[i][j]表示i依赖j的花费
- int dist[MAX][MAX],limit[MAX],cost[MAX];
- void Initial() {
- //初始化
- int i,j;
- for (i = 0; i <= n; ++i)
- tree[i].clear(),best[i] = INF;
- for (i = 1; i <= n; ++i)
- for (j = 1; j <= n; ++j)
- dp[i][j] = INF;
- }
- void CountDist(int s,int pa,int dis){
- //先搜一次记录每个点到其他点的距离
- dist[cur][s] = dis;
- for (int i = 0; i < tree[s].size(); ++i) {
- int v = tree[s][i].v;
- int len = tree[s][i].len;
- if (v == pa) continue;
- CountDist(v,s,dis+len);
- }
- }
- void Tree_DP(int s,int pa) {
- int i,j,k;
- for (i = 0; i < tree[s].size(); ++i)
- if (tree[s][i].v != pa)
- Tree_DP(tree[s][i].v,s);
- for (i = 1; i <= n; ++i) //枚举
- if (dist[s][i] <= limit[s]) {
- dp[s][i] = cost[i];
- for (j = 0; j < tree[s].size(); ++j) {
- //把子树信息汇总到当前点
- int v = tree[s][j].v;
- if (v == pa) continue;
- dp[s][i] += min(dp[v][i]-cost[i],best[v]);
- }
- best[s] = min(best[s],dp[s][i]);//状态转移方程，结果存储在best中
- }
- }
- int main()
- {
- int i,j,k,a,b,c,t;
- scanf("%d",&t);
- while (t--) {
- scanf("%d",&n);
- Initial();
- for (i = 1; i <= n; ++i)
- scanf("%d",&cost[i]);
- for (i = 1; i <= n; ++i)
- scanf("%d",&limit[i]);
- for (i = 1; i < n; ++i) {
- scanf("%d%d%d",&a,&b,&c);
- now.v = b,now.len = c;
- tree[a].push_back(now);
- now.v = a,now.len = c;
- tree[b].push_back(now);
- }
- for (i = 1; i <= n; ++i)
- cur = i,CountDist(i,0,0);
- Tree_DP(1,0);
- printf("%d\n",best[1]);
- }
- }