POJ 2152 Fire

Fire

Time Limit: 2000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 2152
64-bit integer IO format: %lld      Java class name: Main

 

Country Z has N cities, which are numbered from 1 to N. Cities are connected by highways, and there is exact one path between two different cities. Recently country Z often caught fire, so the government decided to build some firehouses in some cities. Build a firehouse in city K cost W(K). W for different cities may be different. If there is not firehouse in city K, the distance between it and the nearest city which has a firehouse, can’t be more than D(K). D for different cities also may be different. To save money, the government wants you to calculate the minimum cost to build firehouses.

 

Input

The first line of input contains a single integer T representing the number of test cases. The following T blocks each represents a test case. 

The first line of each block contains an integer N (1 < N <= 1000). The second line contains N numbers separated by one or more blanks. The I-th number means W(I) (0 < W(I) <= 10000). The third line contains N numbers separated by one or more blanks. The I-th number means D(I) (0 <= D(I) <= 10000). The following N-1 lines each contains three integers u, v, L (1 <= u, v <= N，0 < L <= 1000), which means there is a highway between city u and v of length L. 

 

Output

For each test case output the minimum cost on a single line.

 

Sample Input

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

Sample Output

2
1
2
2
3

Source

POJ Monthly,Lou Tiancheng

 

解题：楼教主的题目真的很难

 

参考这位大牛的博客

 

$dp[i][j]表示结点i靠j消防，best[i]表示以i为根的子树的每个节点以u内的某个节点作为负责站的最小花费$

 

$$best[u] = min(dp[u][i])  i in subtree(u)$$

 

$if dis(u,i) > d_u ,u 不能靠i来消防$

$if dis(u,i) leq d_u,这时候u可以靠i来消防，u的儿子也可以靠i来消防，儿子也可以靠自己内部的点来消防$

$初始化条件 dp[u][i]  = dis(u,i) leq limit[u]?cost[u]:+infty$

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1010;
const int INF = 0x3f3f3f3f;
struct arc{
    int to,w,next;
    arc(int x = 0,int y = 0,int z = -1){
        to = x;
        w = y;
        next = z;
    }
}e[maxn*2];
int head[maxn],w[maxn],d[maxn],best[maxn],dis[maxn][maxn],tot,n;
int dp[maxn][maxn],m;
void add(int u,int v,int w){
    e[tot] = arc(v,w,head[u]);
    head[u] = tot++;
}
void dfs(int u,int fa,int dd,int root){
    dis[root][u] = dd;
    for(int i = head[u]; ~i; i = e[i].next){
        if(e[i].to == fa) continue;
        dfs(e[i].to,u,dd + e[i].w,root);
    }
}
void solve(int u,int fa){
    for(int i = 1; i <= n; ++i)
        if(dis[u][i] <= d[u]) dp[u][i] = w[i];
    for(int i = head[u]; ~i; i = e[i].next){
        if(e[i].to == fa) continue;
        solve(e[i].to,u);
        for(int j = 1; j <= n; ++j)
            if(dis[u][j] <= d[u]) 
                dp[u][j] += min(dp[e[i].to][j] - w[j],best[e[i].to]);
    }
    for(int i = 1; i <= n; ++i) best[u] = min(best[u],dp[u][i]);
}
int main(){
    int kase,u,v,ww;
    scanf("%d",&kase);
    while(kase--){
        memset(head,-1,sizeof head);
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i)
            scanf("%d",w + i);
        for(int i = 1; i <= n; ++i)
            scanf("%d",d + i);
        tot = 0;
        for(int i = 1; i < n; ++i){
            scanf("%d%d%d",&u,&v,&ww);
            add(u,v,ww);
            add(v,u,ww);
        }
        memset(dp,0x3f,sizeof dp);
        memset(best,0x3f,sizeof best);
        for(int i = 1; i <= n; ++i) dfs(i,-1,0,i);
        solve(1,-1);
        printf("%d
",best[1]);
    }
    return 0;
}