题意:n个城市n-1条边 组成一棵树 在每个城市修建消防站会有一个花费costi
每个城市能防火当且仅当地图上距离他最近的消防站距离小于di
问如何修建消防站 使地图上所有的城市都有预防火灾的能力
题解: 这个题太难了..... 完全不会
具体来说就是用dp[i][j]表示在处理i这个城市的时候在j城市修消防站
如果dis i,j > di 那么表示这样修不合法就让dp[i][j] = INF
如果合法这样就已经确定了两个状态
那么我们同样采用先递归再回溯更新的方法 用ans[i]表示包含i的这棵子树已经处理好的最小值
那么回溯时肯定是由他的儿子转移过来
可以直接更新 dp[i][j] += ans[v] 最后dp[i][j] += costj
但可能有一种重复的情况 即j这个消防站既能保护i也能v
所以这种情况就是dp[i][j] += dp[v][j] - costj 减去重复计算的花费
最后再更新ans[i] = min(dp[i][j]）j从1 - n
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; const int INF = 2000000009; int n; int cost[1005]; int d[1005]; int dis[1005]; int head[1005]; int ans[1005]; int dp[1005][1005]; struct node { int to, nex, val; }E[2005]; void dfs1(int x, int fa) { int c = head[x]; for(int i = c; i; i = E[i].nex) { int v = E[i].to; if(v == fa) continue; dis[v] = dis[x] + E[i].val; dfs1(v, x); } } void dfs2(int x, int fa) { int c = head[x]; for(int i = c; i; i = E[i].nex) { int v = E[i].to; if(v == fa) continue; dfs2(v, x); } dis[x] = 0; dfs1(x, -1); for(int i = 1; i <= n; i++) { if(dis[i] > d[x]) { dp[x][i] = INF; continue; } for(int j = c; j; j = E[j].nex) { int vv = E[j].to; if(vv == fa) continue; dp[x][i] += min(ans[vv], dp[vv][i] - cost[i]); } dp[x][i] += cost[i]; } for(int i = 1; i <= n; i++) ans[x] = min(ans[x], dp[x][i]); } int main() { int T; scanf("%d", &T); while(T--) { memset(dp, 0, sizeof(dp)); memset(ans, 63, sizeof(ans)); memset(head, 0, sizeof(head)); int cnt = 0; scanf("%d", &n); 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 = 1; i < n; i++) { int u, v, o; scanf("%d%d%d", &u, &v, &o); E[++cnt].to = v; E[cnt].nex = head[u]; head[u] = cnt; E[cnt].val = o; E[++cnt].to = u; E[cnt].nex = head[v]; head[v] = cnt; E[cnt].val = o; } dfs2(1, -1); printf("%d ", ans[1]); } return 0; }