POJ 2152 fire / SCU 2977 fire（树型动态规划）

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

Http

POJ:https://vjudge.net/problem/POJ-2152

SCU:https://vjudge.net/problem/SCU-2977

Source

树型动态规划

题目大意

n个城市由n-1条带权的路相连接，现在要选择一些城市建造消防站，每个城市建造消防站都有不同的花费，并且要满足没有建消防站的城市u在D[u]范围内有建了消防站的城市（每个城市的D[u]也有可能不一样），现在求花费最小的方案。

解决思路

看到这个题目的第一眼想到的是最小支配集，但要注意题中在D[u]范围内这个条件，我们不能用简单的最小支配集算法来解决。

在开始讲述前，我们先规定几个变量及其意义。

F[u][build]：这是我们动态规划的数组，其意义是选择在build处修建消防站来覆盖u的最小花费（并保证此时u的所有子树都已经被覆盖）

Best[u]：表示覆盖u的所有方案中花费最小的一个

Dist[u][v]：u和v之间的距离

首先我们来看稍微好理解一点的Best[u]，根据定义，对于所有的满足Dist[u][build]< D[u]的我们可以得到Best[u]=min(Best[u],Dist[u][build])。这是可以直接根据定义推导出来的。

那么接下来就是求F[u][build]啦。

当然首先是要递归地求出u的子节点（下文中均用v来表示）的信息。

接下来就是最重要的部分了，有点难理解，仔细阅读！

然后我们枚举图中的每一个点build，表示在build建消防站来覆盖点u。若Dist[u][build]>D[u]，说明在build建立消防站不能覆盖点u，那么我们就把F[u][build]置为无穷大。若Dist[u][build]< D[u]，说明可以在build建立消防站来覆盖点u，我们就依次枚举u的子节点v，让F[u][build]每次累加min(Best[v],F[v][build]-W[build]），最后再让F[u][build]加上建站在build的费用W[build]。下面来解释一下这个转移是如何进行的，又是基于什么原理。

因为在build建立消防站后可能不止覆盖到u，还有可能同时可以覆盖u的子节点v，那么此时v就有两种选择，一是被build覆盖（即上面的F[v][build]-W[build]，你问我为什么要减去W[build]，因为F[v][build]中是统计了建站在build时的费用的，为了防止重复计算建立消防站在build的费用，所以这里要减去）；二是被其他点覆盖（即上面的Best[v]）。

另外如果build无法覆盖v怎么办（即Dist[v][build]>D[v]），上面的方程好像没有考虑到这种情况啊？

不用担心，若build无法覆盖v，此时的F[v][build]是置为无穷大的，取min后不会被统计到F[u][build]中。

最后，为了节省空间，在笔者的代码中，Dist转换成了一维的，Dist[v]表示当前dfs中的点u到v的距离。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

const int maxN=1001;

const int inf=2147483647;

class Edge

{

public:

    int v,w;

};

int n;

int W[maxN];

int D[maxN];

vector<Edge> E[maxN];

int Dist[maxN];

int F[maxN][maxN];

int Best[maxN];

queue<int> Q;

int read();

void dfs(int u,int father);

int main()

{

    int TT;

    TT=read();

    for (int ti=1;ti<=TT;ti++)

    {

        n=read();

        for (int i=1;i<=n;i++)//注意多组数据记得清空

            E[i].clear();

        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 x=read(),y=read(),w=read();

            E[x].push_back((Edge){y,w});

            E[y].push_back((Edge){x,w});

        }

        //cout<<"Read_end"<<endl;

        dfs(1,1);

        cout<<Best[1]<<endl;

    }

    return 0;

}

int read()

{

    int x=0;

    int k=1;

    char ch=getchar();

    while (((ch<'0')||(ch>'9'))&&(ch!='-'))

        ch=getchar();

    if (ch=='-')

    {

        k=-1;

        ch=getchar();

    }

    while ((ch>='0')&&(ch<='9'))

    {

        x=x*10+ch-48;

        ch=getchar();

    }

    return x*k;

}

void dfs(int u,int father)

{

    for (int i=0;i<E[u].size();i++)//首先把所有子节点的值算出来

    {

        int v=E[u][i].v;

        if (v==father)

            continue;

        dfs(v,u);

    }

    memset(Dist,-1,sizeof(Dist));//临时用bfs求出u到所有点的距离

    while (!Q.empty())

        Q.pop();

    Dist[u]=0;

    Q.push(u);

    do

    {

        int uu=Q.front();

        Q.pop();

        for (int i=0;i<E[uu].size();i++)

        {

            int v=E[uu][i].v;

            if (Dist[v]==-1)

            {

                Dist[v]=Dist[uu]+E[uu][i].w;

                Q.push(v);

            }

        }

    }

    while (!Q.empty());

    Best[u]=inf;//因为要求最小，所以初值为无穷大

    for (int build=1;build<=n;build++)

    {

        if (Dist[build]<=D[u])

        {

            F[u][build]=W[build];

            for (int i=0;i<E[u].size();i++)

            {

                int v=E[u][i].v;

                if (v==father)

                    continue;

                F[u][build]+=min(Best[v],F[v][build]-W[build]);//统计u的子节点v

            }

            Best[u]=min(Best[u],F[u][build]);//用刚计算出来的F[u][build]更新Best[u]

        }

        else//若build无法覆盖u，则置为无穷大

            F[u][build]=inf;

    }

    return;

}

巴特西

POJ 2152 fire / SCU 2977 fire（树型动态规划）

POJ 2152 fire / SCU 2977 fire（树型动态规划）

Description

Input

Output

Sample Input

Sample Output

Http

Source

题目大意

解决思路

代码

最新文章

热门文章