hdu 4003 Find Metal Mineral 【树形dp，分组背包】

淡淡的烟草味﹌ 2022-09-21 00:29 132阅读 0赞

题目：[hdu 4003 Find Metal Mineral ][hdu 4003 Find Metal Mineral]

题意：火星上发现了一些n个矿厂，有 k 个机器人从 s 点出发采矿，给出路段间的花费cost，求最小的花费采所有的矿。

分类：树形dp + 分组背包

分析：结论1：假如我们从 i点出发k个机器人采完以 k 为根节点的所有矿又回到 i 点，那么花费为 i 为根节点的cost 的和 乘以 k。

对于每个节点，定义状态：dp【i】【j】 用 j 个机器人去采以 i 为根节点的子树的所有矿石的最小花费

状态转移方程：dp【father】【num】 = min（dp【father】【num】，dp【father】【num-k】+dp【child.to】【k】+k\*child.cap）；

其中num为father节点枚举机器人数量，k为child节点枚举机器人数量，num-k为father节点除了k个给child给其他孩子节点的机器人。

注意：在转移过程中的初始化、可以通过结论1来优化。

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <string>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 10100;
    
    struct Node
    {
        int to;
        int cap;
    };
    vector<Node> v[N];
    int dp[N][12],vis[N]; ///dp[i][0] 为从下往上最短距离 dp[i][1] 为从下往上此短距离 dp[i][2] 为从经过root最短距离
    int n,s,k;
    void creat(int father)
    {
        vis[father]=1;
        for(int i=0;i<v[father].size();i++)
        {
            Node child=v[father][i];
            if(vis[child.to]==1)
                continue;
            creat(child.to);
            for(int num=k;num>=0;num--) //注意0
            {
                dp[father][num]+=dp[child.to][0]+2*child.cap;//最大结果
                for(int j=1;j<=num;j++)
                    dp[father][num]=min(dp[father][num],dp[father][num-j]+dp[child.to][j]+j*child.cap);//派j个机器人给v子树就会经过father-child之间的边j次
            }
        }
    }
    int main()
    {
        while(~scanf("%d%d%d",&n,&s,&k))
        {
            for(int i=0;i<n-1;i++)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                Node tmp;
                tmp.to=y,tmp.cap=z;
                v[x].push_back(tmp);
                tmp.to=x;
                v[y].push_back(tmp);
            }
            Del(vis,0);Del(dp,0);
            creat(s);
            printf("%d\n",dp[s][k]);
            for(int i=1;i<=n;i++)
                v[i].clear();
        }
        return 0;
    }

[hdu 4003 Find Metal Mineral]: http://acm.hdu.edu.cn/showproblem.php?pid=4003