HDU 4003 Find Metal Mineral

标签：eof   space   重复   miner   ++   cpp   clu   for   code   

题意：用k个机器人去遍历有n个节点的有根树，边权代表一个机器人通过这条边的代价，求最小代价。

\(k\le 10\)

背包走起

\(f_{u,i}\) 表示遍历完完 \(u\) 子树后留 \(i\) 个机器人在 \(u\) 子树内，\(v\) 是 \(u\) 的子节点，\(val_{u,v}\) 表示 \(u \leftrightarrow v\) 的边权
\[ f_{u,i}=\min(f_{v,0}+2\times val_{u,v},\min \{ f_{u,i-j}+f_{v,j}+j\times val_{u,v} \}) \]
对于 \(f_{v,0}+2\times val_{u,v}\)，很显然，派一只机器人去 \(v\) 子树逛一圈回来即 \(f_{v,0}\)，通过 \(u \leftrightarrow v\) 两次即 \(2\times val_{u,v}\)

对于后面那个柿子，枚举要留 \(j\) 个机器人在 \(v\) 子树内，那么其实就派 \(j\) 个机器人过去就完事了，通过 \(u \rightarrow v\) 共 \(j\) 次

注意枚举顺序，不要单棵子树重复计算了

答案就是 \(f_{s,k}\)

// This code writed by chtholly_micromaker(MicroMaker)
#include 
#define reg register
using namespace std;
const int MaxN=10050;
struct Edge
{
    int nxt,to,w;
}E[MaxN inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(sy)
        x=y;
    return;
}
inline void dfs(int u,int fa)
{
    for(int i=hd[u];~i;i=E[i].nxt)
    {
        reg int v=E[i].to;
        if(v==fa)
            continue;
        dfs(v,u);
        for(int V=k;V>=0;--V)
        {
            f[u][V]+=f[v][0]+2*E[i].w;
            for(int j=0;j>n>>s>>k)
        work();
    return 0;
}

HDU 4003 Find Metal Mineral

标签：eof   space   重复   miner   ++   cpp   clu   for   code   

原文地址：https://www.cnblogs.com/chinesepikaync/p/12401456.html