【樹形DP】 POJ 2152 Fire

Fire

Time Limit: 2000MS	Memory Limit: 65536K
Total Submissions: 1412	Accepted: 751

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 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的題目，詳解可以在陳啟峰的2006國家集訓隊論文中看到。

這道題花費了我很多時間，無論是陳啟峰的論文，解題報告，還是其他人的題解，都有接觸過一些。

說實話，難受。而且完全沒有之後能做出相同題目的自信。

----------------------------------------以下，正題--------------------------------------------------------------------------

題意大概是講某個國家最近有人喜歡玩火（笑）是以需要建設消防站的故事，條件在下面會分析而且如果隻是來看翻譯就想做題的話推薦你直接換題吧就是這樣。

首先我們要了解題目給出的條件：

1、每個城市可以建造消防站點，對于城市k來說消耗為w[k]。

2、每個城市可以選擇距離自己最近的一個一定距離内的消防站作為負責自己的消防站，對于城市k來說距離不能超過d[k]。

3、每個城市需要有至少需要一個負責的消防站。

因為是樹形DP是以轉換成有根樹。

首先，對于條件2，3，我們可以看作“距離k以記憶體在一個消防站作為負責站點”就行了。因為其實隻要範圍記憶體在一個站點，就可以滿足條件。

然後，我們來分析我們設定的狀态和狀态的轉移。

設定狀态dp[i][j]，表示城市i以j為負責站點的情況下的最優解，用best。那麼此時的情況就有三種：

③ 如果j是i的父節點，那麼對于i的直接子節點k，k可以選取點j為負責站或者選取自己的子樹中的元素作為負責站。

即 dp[i][j]+=min(dp[k][j],best[k])

⑥ 如果點j就是點i，那麼對于i的直接子節點k，k同樣可以選取點j作為負責站，或者選擇子樹的元素作為負責站，不過要加上修建站點的花費。

即 dp[i][j]+=w[i]+min(dp[k][j],best[k])

之是以隻從那個dp[k][j]轉換，是因為負責站點在設定上至少是距離最近的點，是以在非k點子節點的時候距離最近的必然是點j。

⑨ 如果j是i的子節點，那麼對于i的子節點k，分為含j的子樹和不含j的子樹。其中不含j的子樹跟第一種相同；對于含j的子樹，

則有 dp[i][j]+=dp[k][j]

理由和前面的類似，也是因為最短。

明明打算寫的簡單易懂但是感覺還是講不清楚。。。

代碼如下

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>

using namespace std;

const int MAXN=2005;
const int MAXM=1005;
const int INF=0x3f3f3f3f;

int n;
int cost[MAXM];
int D[MAXM];

int e_max;
int u[MAXN],v[MAXN],w[MAXN],nex[MAXN];
int fir[MAXM];

void add_edge(int a,int b,int c)
{
    int e=e_max++;
    u[e]=a;
    v[e]=b;
    w[e]=c;
    nex[e]=fir[a];
    fir[a]=e;
}

int dp[1005][1005];
int dis[1005];
int point[1005];

void DfsDis(int x,int father,int len,int mark)
{
    //printf("%d %d %d\n",x,father,len);
    dis[x]=len;
    point[x]=mark;
    for(int e=fir[x];~e;e=nex[e])
    {
        if(v[e]==father) continue;
        DfsDis(v[e],x,len+w[e],mark);
    }
}

int best[MAXM];

void Dfs(int x,int father)
{
    //printf("++%d  %d++\n",x,father);
    for(int e=fir[x];~e;e=nex[e])
    {
        if(v[e]==father) continue;
        Dfs(v[e],x);
    }

    point[x]=x;
    dis[x]=0;
    for(int e=fir[x];~e;e=nex[e])
        DfsDis(v[e],x,w[e],v[e]);

    /*
    for(int i=1;i<=5;i++) printf("%d  %d\n",point[i],dis[i]);
    system("pause");
    */

    for(int i=1;i<=n;i++)
    {
        dp[x][i]=0;
        if(dis[i]>D[x]) dp[x][i]=INF;
        else if(point[i]==father)
        {
            for(int e=fir[x];~e;e=nex[e])
                dp[x][i]+=min(dp[v[e]][i],best[v[e]]);
        }
        else if(x==i)
        {
            //cout<<x<<" "<<i<<endl;
            dp[x][i]+=cost[x];
            for(int e=fir[x];~e;e=nex[e])
                dp[x][i]+=min(dp[v[e]][i],best[v[e]]);
        }
        else
        {
            for(int e=fir[x];~e;e=nex[e])
            {
                if(v[e]==point[i])
                {
                    dp[x][i]+=dp[point[i]][i];
                    continue;
                }
                dp[x][i]+=min(dp[v[e]][i],best[v[e]]);
            }
        }
    }

    best[x]=INF;
    for(int i=1;i<=n;i++)
    {
        if(point[i]!=father)
        {
            best[x]=min(dp[x][i],best[x]);
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(dp,0,sizeof dp);
        memset(fir,-1,sizeof fir);
        e_max=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&cost[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&D[i]);
        }
        for(int i=0;i<n-1;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add_edge(u,v,w);
            add_edge(v,u,w);
        }

        Dfs(1,0);


//        for(int i=1;i<=n;i++)
//        {
//            for(int j=1;j<=n;j++)
//                printf("%d ",dp[i][j]);
//            printf("\n");
//        }


        printf("%d\n",best[1]);
    }
    return 0;
}