树上分组背包

题意:给定一棵n个节点的树,树的某个节点s上有k个机器人。要分配这些机器人去遍历这颗树,求经过的边的最小权值和。

分析:对于某一棵子树,如果进去一个机器人,它要么出来,要么不出来。如果有一个机器人出来了,就不能有第二个机器人出来。因为让第一个人去走第二个人要走的路,比第二个人自己走再走出来肯定要优(证:如果第一个人单独走,走过的每一条边只经过两遍,如果两个人走一个人走的路,既然都要进去出来,那么出口处的路会经过4遍,比前者差,证毕)。因此第二个人就可以不进入这棵树。所以我们可以得到一个优美而且正确而且高效率的函数:

$f(i,j)$

$f(i,j)$表示i节点进去不出来j个机器人。如果j等于0的话表示进去一个人出来。所以有$f(i,j)=min(∑(f(k,l)+w(i,k))(∑l=j,(i,k)∈E))$,这其实就是一个分组的背包问题,物品是子节点的j值,每个子节点是一组,要达到当前节点j值同时最小化$f(i,j)$。于是时间复杂度为: $O(nk^2)$

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 10000

using namespace std;

int u[MX*2],v[MX*2],w[MX*2];
int fst[MX+1],nxt[MX*2],lnum,n,s,k;
int f[MX][11];

void addeg(int nu,int nv,int nw)
{
    nxt[++lnum]=fst[nu],fst[nu]=lnum,u[lnum]=nu,v[lnum]=nv,w[lnum]=nw;
}

void dfs(int node,int fat)
{
    for(int i=fst[node];i!=-1;i=nxt[i])
    {
        if(v[i]==fat)continue;
        dfs(v[i],node);
        for(int j=k;j>=0;j--)
        {
            f[node][j]+=f[v[i]][0]+w[i]*2;
            for(int l=1;l<=j;l++)f[node][j]=min(f[node][j],f[node][j-l]+f[v[i]][l]+l*w[i]);
        }
    }
}

int main()
{
    int a,b,c;
    while(cin>>n>>s>>k)
    {
        memset(fst,0xff,sizeof(fst)),memset(f,0,sizeof(f)),lnum=-1;
        for(int i=1;i<n;i++)scanf("%d%d%d",&a,&b,&c),addeg(a,b,c),addeg(b,a,c);
        dfs(s,0),printf("%d\n",f[s][k]);
    }
    return 0;
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *