HDU4003 Find Metal Mineral

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)

Total Submission(s): 759 Accepted Submission(s): 298

Problem Description

Humans have discovered a kind of new metal mineral on Mars which are distributed in point‐like with paths connecting each of them which formed a tree. Now Humans launches k robots on Mars to collect them, and due to the unknown reasons, the landing site S of all robots is identified in advanced, in other word, all robot should start their job at point S. Each robot can return to Earth anywhere, and of course they cannot go back to Mars. We have research the information of all paths on Mars, including its two endpoints x, y and energy cost w. To reduce the total energy cost, we should make a optimal plan which cost minimal energy cost.

Input

There are multiple cases in the input.

In each case:

The first line specifies three integers N, S, K specifying the numbers of metal mineral, landing site and the number of robots.

The next n‐1 lines will give three integers x, y, w in each line specifying there is a path connected point x and y which should cost w.

1<=N<=10000, 1<=S<=N, 1<=k<=10, 1<=x, y<=N, 1<=w<=10000.

Output

For each cases output one line with the minimal energy cost.

Sample Input

3 1 1

1 2 1

1 3 1

3 1 2

1 2 1

1 3 1

Sample Output

Hint

In the first case: 1->2->1->3 the cost is 3;

In the second case: 1->2; 1->3 the cost is 2;

************************************************************************************

这个是2011大连赛区网络赛的第三道。

题目大意：给定k个机器人去遍历n个节点的树，求最小花费

一开始不会，看了大牛的才懂。实在惭愧，看得太认真了，结果自己写程序就长得和大牛程序几乎一样了。

一道很好的树形dp

dp[pos][num]表示以pos为根节点的子树下，用去num个机器人，所得到的最小值

特别的是当num==0的时候，dp[pos][0]表示用一个机器人去走完所有子树，最后又回到pos这个节点

状态转移：dp[pos][num]=min∑{dp[pos_j][num_j]+w_j},pos_j是pos的所有儿子，

当num_j==0的时候，和别的时候不同，特别处理一下就好。

状态转移并不难，最精华的，我不认为是状态转移，而是转移时使用的那个“分组背包”思想。

使用一维数组的“分组背包”伪代码如下：

for 所有的组i

for v=V..0

for 所有的k属于组i

f[v]=max{f[v],f[v-c[k]]+w[k]}

上面那个状态转移时，要把num个机器人分给所有它的儿子，状态太多了，不好做，用“分组背包”实在太帅了。

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MIN(a,b) ((a)<(b)?(a):(b))

int id,head[10001];
int n,s,k;
int dp[10001][11];

struct Edge
{
    int ed,val,nxt;
}edge[20001];

void add_edge(int sta,int ed,int val)
{
    edge[id].ed=ed;
    edge[id].val=val;
    edge[id].nxt=head[sta];
    head[sta]=id++;
}

void dpt(int pos,int pre)
{
    int mark=0;
    for(int i=head[pos];~i;i=edge[i].nxt)
        if(edge[i].ed!=pre)
            dpt(edge[i].ed,pos),mark=1;
    if(mark==0)return ;
    /*这以下就是用“分组背包”的状态转移，
    3个for就对应了“分组背包”的那3个循环*/
    for(int i=head[pos];~i;i=edge[i].nxt)
    {
        int t=edge[i].ed;
        if(t==pre)continue;
        for(int j=k;j>=0;j--)
        {
            if(j==0)dp[pos][0]+=dp[t][0]+2*edge[i].val;
            else
            {
                dp[pos][j]+=dp[t][0]+2*edge[i].val;
                for(int u=1;u<=j;u++)
                    dp[pos][j]=MIN(dp[pos][j],dp[pos][j-u]+dp[t][u]+u*edge[i].val);
            }
        }
    }
}

int main()
{
    while(scanf("%d%d%d",&n,&s,&k)==3)
    {
        memset(head,-1,sizeof(head));
        memset(edge,0,sizeof(edge));
        memset(dp,0,sizeof(dp));
        id=0;
        for(int i=1;i<n;i++)
        {
            int sta,ed,val;
            scanf("%d%d%d",&sta,&ed,&val);
            add_edge(sta,ed,val);
            add_edge(ed,sta,val);
        }
        dpt(s,0);
        printf("%d\n",dp[s][k]);
    }
}