【POJ 2152】 Fire

【题目链接】

点击打开链接

【算法】

同样是树形DP，但是比较难，笔者做这题看了题解

令f[i][j]表示在以i为根的子树中

1.在以i为根的子树中建一些消防站

2.在节点j必须建一个消防站

3.以i为根的子树中，每个节点在满足距离不超过D的前提下，选一个子树内的节点或节点j作为“负责站”

4.节点i的负责站必须是节点j

的最小代价

考虑转移，为了转移方便，我们用一个辅助状态best[i]表示以i为根的子树中，每个节点在满足距离不超过D的前提下，

选一个子树内的节点作为“负责站”的最小代价,显然 : best[i] = min{f[i][j]}（j在以i为根的子树中）

当dis(i,j) > Di时，f[i][j] = +oo(正无穷，表示不存在这种状态

当dis(i,j) <= Di时，它的每个子节点k有两种选择 :

1.选择子树内的节点为“负责站”，代价为best[k]

2.选择j为它的“负责站”，代价为f[k][j]

因此f[i][j] = w[j] + sigma(min{best[k],f[k][j]}) (k为i的孩子）

最后，best[1]就是答案

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 1010

const int INF = 2e9;

int i,T,n,u,v,l;

vector< pair<int,int> > e[MAXN];

int dis[MAXN],best[MAXN],w[MAXN],d[MAXN],f[MAXN][MAXN];

inline void getdist(int x)

{

        int i,y;

        for (i = ; i < e[x].size(); i++)

        {

                y = e[x][i].first;

                if (dis[y] == -)

                {

                        dis[y] = dis[x] + e[x][i].second;

                        getdist(y);

                }

        }

}

inline void dfs(int x,int fa)

{

        int i,j,y;

        for (i = ; i < e[x].size(); i++)

        {

                y = e[x][i].first;

                if (fa != y) dfs(y,x);

        }

        for (i = ; i <= n; i++) dis[i] = -;

        dis[x] = ;

        getdist(x);

        best[x] = INF;

        for (i = ; i <= n; i++) f[x][i] = INF;

        for (i = ; i <= n; i++)

        {

                if (dis[i] <= d[x])

                {

                        f[x][i] = w[i];

                        for (j = ; j < e[x].size(); j++)

                        {

                                y = e[x][j].first;

                                if (fa != y) f[x][i] += min(best[y],f[y][i]-w[i]);

                        }

                        best[x] = min(best[x],f[x][i]);

                }

        }

}

int main()

{

        scanf("%d",&T);

        while (T--)

        {

                scanf("%d",&n);

                for (i = ; i <= n; i++) e[i].clear();

                for (i = ; i <= n; i++) scanf("%d",&w[i]);

                for (i = ; i <= n; i++) scanf("%d",&d[i]);

                for (i = ; i < n; i++)

                {

                        scanf("%d%d%d",&u,&v,&l);

                        e[u].push_back(make_pair(v,l));

                        e[v].push_back(make_pair(u,l));

                }

                dfs(,);

                printf("%d\n",best[]);

        }

        return ;

}

巴特西

【POJ 2152】 Fire

最新文章

热门文章