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; }

转载于:https://www.cnblogs.com/SYCstudio/p/7149180.html