首页 > 搜索 > DFS搜索 > HDU 3907-Replica Placement-动态规划-[解题报告]HOJ
2015
04-14

HDU 3907-Replica Placement-动态规划-[解题报告]HOJ

Replica Placement

问题描述 :

Topsky wants to build a content delivery network. It contains an origin server and some mirror servers as shown in figure 1. Original data is put at the origin server (root in figure 1) while replicas are put at some of the mirror servers (node 2 and 5 in figure 1). When a node issues a request of data, it will try to find its destination in following steps.
1.  Check if there is a replica at its own place. If yes, the request meets. Otherwise do step 2.
2.  Forward the request to its parent, and let its parent do step 1.
Girls’ Party

The cost of meeting the request C (v) is defined as the sum of weight of the edges along the road. If C (v) is not greater than an upper bound Q (v), then the retrieval cost is satisfied. Topsky further assumes a nonnegative cost S (v) which means the cost of storing data at node v. Note that the origin server is special, the cost of storing data at origin server is 0. Now Topsky wants to find the way of replicas placement such the retrieval cost of all nodes are satisfied while the total storage cost is minimal.

输入:

The first line contains a single integer T (T <= 20), indicating the number of test cases.
Each case begins with three integers N (1<= N <= 1000) indicates the number of servers.
Then N lines follow. Each line contains four integers Fv (0 <= Fv <= N), Qv, Sv and Wv (0 <= Qv, Sv, Wv <= 105). In line i (1 <= i <= N), Fv is the father of node i (if Fv is 0, it means node i is the origin server, Qv is -1, Sv is 0 and Wv is 0), Qv is upper bound of retrieval cost, Sv is storing cost of node i and Wv is weight of this edge between node i and node Fv.

输出:

The first line contains a single integer T (T <= 20), indicating the number of test cases.
Each case begins with three integers N (1<= N <= 1000) indicates the number of servers.
Then N lines follow. Each line contains four integers Fv (0 <= Fv <= N), Qv, Sv and Wv (0 <= Qv, Sv, Wv <= 105). In line i (1 <= i <= N), Fv is the father of node i (if Fv is 0, it means node i is the origin server, Qv is -1, Sv is 0 and Wv is 0), Qv is upper bound of retrieval cost, Sv is storing cost of node i and Wv is weight of this edge between node i and node Fv.

样例输入:

1
3
0 -1 0 0
1 1 1 1
2 1 1 1

样例输出:

1

其实就是一道很简单的树DP,但是这种类型我掌握的不好……比赛的时候一度认为这是难题……坚持不可做,而没有看

题意概述:给定一课带权树,根节点有一个server,在每个节点安放一个副本需要一个s[i],每个节点必须有一个他的祖先节点或者他本身为他提供副本,为了保证安全这个副本离他的距离不超过q[i],求最小的费用

状态的设计没遇到过这样的(见识短了吧……)

状态设计dp[i][j]表示第i个节点为根的子树在最早在其祖先j处有一个控制节点的的最小花费。

对于叶子节点,如果j是其不可达节点(边权和小于q[i])那么 dp[i][j] = 0;反之dp[i][j] = s[i];特别的有dp[i][i] = s[i];

然后对于非叶子节点(关键了,有一个地方写错了一个晚上……)

如果是dp[i][i] = s[i] + 从儿子的转移费用。

如果是dp[i][j] j是其可达节点dp[i][j] = 从儿子转移的费用 于 dp[i][i]的最小值!!注意事项(1)

如果是dp[i][j] j是不可达节点 dp[i][j] = 从儿子的转移费用 + s[i];

然后关键是怎么算儿子节点的费用。

对于一个状态j i的儿子节点的费用是 dp[son(i)][son(i)] 与 dp[son(i)][j]的最小值……注意事项(2)

如果都注意了以上的问题,估计就不会有错了……

代码如下:

/*
 * =====================================================================================
 *
 *       Filename:  dp.cpp
 *
 *    Description:  Problem A on ChengDu
 *
 *        Version:  1.0
 *        Created:  2011/6/23 21:11:48
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  ronaflx
 *        Company:  hit-acm-group
 *
 * =====================================================================================
 */
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <list>
#include <string>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <stdexcept>
#include <utility>
#include <cassert>
#include <complex>
using namespace std;
#define DEBUG(x) cout << #x << " " << x << endl
#define LEFT(i) ((i) << 1)
#define RIGHT(i) (((i) << 1) | 1)
#define MID(i) ((l[i] + r[i]) >> 1)
#define CC(i, v) memset(i, v, sizeof(i))
#define REP(i, l, n) for(int i = l;i < int(n);++i)
#define FOREACH(con, i) for(__typeof(con.begin()) i = con.begin();i != con.end();++i)
const int INF = 100000000;
const int N = 1008;
int dp[N][N];
vector<int> adj[N];
int s[N], q[N], f[N], n, w[N];
bool isLeaf(int u)
{
    return adj[u].empty();
}

void dfs(int u)
{
    FOREACH(adj[u], i)
        dfs(*i);
    int now = 0, v;
    if(isLeaf(u))
    {
        for(v = u; v != -1;now += w[v], v = f[v])
        {
            if(v == u || now > q[u])
                dp[u][v] = s[u];
            else
                dp[u][v] = 0;
        }
    }
    else
    {
        for(v = u;v != -1;now += w[v], v = f[v])
        {
            int tot = 0;
            FOREACH(adj[u], j)
                tot += min(dp[*j][v], dp[*j][*j]);
            if(u == v || now > q[u])
                dp[u][v] = tot + s[u];
            else
                dp[u][v] = min(tot, dp[u][u]);
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        int root = -1;
        for(int i = 0;i < n;i++) adj[i].clear();
        for(int i = 0;i < n;i++)
        {
            scanf("%d %d %d %d", &f[i], &q[i], &s[i], &w[i]);
            f[i]--;
            if(f[i] == -1)
            {
                root = i;
                q[i] = 0;
            }
            else adj[f[i]].push_back(i);
        }
        dfs(root);
        printf("%d\n", dp[root][root]);
    }
    return 0;
}

  

参考:http://www.cnblogs.com/ronaflx/archive/2011/08/04/2126939.html


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的