문제풀이 보고서

Description 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 1 1 1 1 2 1 2 1 3 4 1 4 1 4 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 2 1 2 1 3 4 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 1 1 1 2 1 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 2 1 2 1 2 1 2 3 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 4 2 Sample 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3고속도로마다 길이가 다를 수 있습니다.도시 i에 대해 이 도시에서 방화소를 건설하는 비용은 w[i]이다. 그리고 반드시 d[i] 범위 내에서 하나의 역(그 자신을 포함) j를 찾아야 한다. 적어도 이런 j역이 존재하고 j역에 방화소를 건설해야 한다. 그러면 i는 j에 의존할 수 있다.우리의 목적은 이러한 네트워크를 구하는 것이다. 모든 도시가 의존하는 방화소가 있고 비용 요구가 가장 적다.
분석: 처음에 이 문제를 받으면 안개가 낀다.np의 알고리즘만 생각할 수 있습니다.나중에 진계봉의 느슨한 문제 풀이 방법을 보고 나서야 이런 유형의 문제를 대충 알 수 있었다.데이터 범위가 1000인 것을 보면 분명히 n^2의 알고리즘이다. 따라서 우리는 spfa로 임의의 두 점 사이의 거리dis[u][v]를 미리 처리한 다음에 나무의 점 분치 사상을 사용한다. 나무를 풀 때 우리는 이 나무의 뿌리 노드와 그의 아들 노드만 주목하고 이 나무의 아버지를 주목하지 않는다. 그러면 후효성 문제를 고려할 필요가 없다.그리고 우리는 상태 dp[i]를 정의할 수 있지만 이렇게 정의한 후에 분명히 옮길 수 없다. 왜냐하면 i가 어느 사이트에 의존하는지 모르기 때문이다.자주 사용하는 방법은 1차원과 dp[i][j]를 추가하는 것이다.위에서 상태는 dp[i][j]로 i를 뿌리로 하는 자수를 나타낼 수 있고 i번째 도시는 j에 의존하고 i자수 중의 다른 노드는 모두 의존하는 노드의 최소 비용을 나타낸다.이 말은 두 가지가 반드시 긴박하고 전체 해 공간의 범위를 좁히는 것이지만, 우리는 먼저 이러한 상태가 반드시 정확하다는 것을 증명해야 한다.(구체적으로 논문을 보며) 그렇다면 문제가 왔다. 옮기는 것은 어떤 것일까?관찰한 바에 의하면 i를 뿌리로 하는 자수를 계산할 때마다 1-n 노드를 매거해야 한다.만약에 우리가 폭력적으로 한다면 매번 i노드는 n을 매거해야 한다. 그의 아들은 여러 가지 결정을 내린다. 그 중 하나는 i나무 안의 노드를 의존소로 하고 다른 하나는 i나무 이외의 노드를 의존소로 한다. 이것은np의 복잡도이다.이것을 생각하니 나는 문제가 다시 원래의 곳으로 돌아간 것을 발견하였다.Orz 자세히 분석해 보자. 매번 뿌리 노드 i에 대한 의존역 v를 매거할 때마다 i역은 반드시 방화소를 건설했다. 그의 자금은 이미 썼다. 만약에 i의 아들 노드가 v를 의존역으로 할 수 있다면 v를 의존역으로 하는 것보다 더 좋은 상황은 없다. 만약에 i의 아들 노드가 v를 의존역으로 할 수 없다면 i의 아들은 반드시 그를 뿌리로 하는 자수 나무의 노드를 의존역으로 삼을 것이다.따라서 보조 dp수 그룹best[i]를 설계하여 i를 뿌리로 하는 나무를 표시하면 제목의 요구를 충족시키는 최소한의 비용이 든다.이렇게 설정하면 몇 가지 조건을 제한하고 공간을 이해하는 범위를 좁혀서 우리는 n^2의 속도 내에서 해답을 구할 수 있다.마지막에 옮겨서 자연스럽게 나왔어요.dp[u][j] = w[j] + sigma( min(dp[v][j] - w[j], best[v]); best[u] = min(best[i], dp[u][j]);

//
//  Created by Running Photon on 2015-09-07
//  Copyright (c) 2015 Running Photon. All rights reserved.
//
//
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x,begin())
#define ll long long
#define CLR(x) memset(x, 0, sizeof x)
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 1e4 + 10;
const int maxv = 1e3 + 10;
const double eps = 1e-9;


inline int read() {
    char c = getchar();
    int f = 1;
    while(!isdigit(c)) {
    if(c == '-') f = -1;
    c = getchar();
    }
    int x = 0;
    while(isdigit(c)) {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int w[maxv], d[maxv];
int head[maxv], nxt[maxn], pnt[maxn], cost[maxn], cnt;
int dp[maxv][maxv], dis[maxv][maxv], best[maxv];
int n;
void add_edge(int u, int v, int val) {
    cost[cnt] = val;
    pnt[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt++;
}
int vis[maxv];
void spfa(int root) {
    for(int i = 1; i <= n; i++) {
        dis[root][i] = inf;
    }
    dis[root][root] = 0;
    queue <int> que;
    que.push(root);
    vis[root] = 1;
    while(que.size()) {
        int u = que.front();
        que.pop();
        vis[u] = 0;
        for(int i = head[u]; ~i; i = nxt[i]) {
            int v = pnt[i];
            if(dis[root][v] > dis[root][u] + cost[i]) {
                dis[root][v] = dis[root][u] + cost[i];
                if(!vis[v]) {
                    vis[v] = 1;
                    que.push(v);
                }
            }
        }
    }
}
void dfs(int u, int fa) {
    for(int i = head[u]; ~i; i = nxt[i]) {
        int v = pnt[i];
        if(v == fa) continue;
        dfs(v, u);
    }
    for(int i = 1; i <= n; i++) {
        if(dis[u][i] <= d[u]) {
            dp[u][i] = w[i];
            for(int j = head[u]; ~j; j = nxt[j]) {
                int v = pnt[j];
                if(v == fa) continue;
                dp[u][i] += min(dp[v][i] - w[i], best[v]);
            }
            best[u] = min(best[u], dp[u][i]);
        }
    }
}
int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    int cas = read();
    while(cas--) {
        CLR(vis); memset(best, 0x3f, sizeof best);
        cnt = 0; memset(head, -1, sizeof head);
        memset(dp, 0x3f, sizeof dp);
        n = read();
        for(int i = 1; i <= n; i++)
            w[i] = read();
        for(int i = 1; i <= n; i++)
            d[i] = read();
        for(int i = 1; i < n; i++) {
            int u = read(), v = read(), val = read();
            add_edge(u, v, val);
            add_edge(v, u, val);
        }
        for(int i = 1; i <= n; i++)
            spfa(i);
        CLR(vis);
        dfs(1, 1);
        printf("%d
", best[1]);
    }

    return 0;
}