Find Metal Mineral
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 2371 Accepted Submission(s): 1079
3 1 1 1 2 1 1 3 1 3 1 2 1 2 1 1 3 1
In the first case: 1->2->1->3 the cost is 3; In the second case: 1->2; 1->3 the cost is 2;
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]}
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; struct Edge{
int to;
int value;
int next;
}edge[*];
int head[],dp[][];
int N,S,K,total; inline int MIN(int a,int b)
{
if(a<b) return a;
return b;
}
void addEdge(int start,int end,int value)
{
edge[total].to=end;edge[total].value=value;
edge[total].next=head[start];head[start]=total++; edge[total].to=start,edge[total].value=value;
edge[total].next=head[end],head[end]=total++;
} void DP(int source,int pre)
{
for(int i=head[source];i!=-;i=edge[i].next)
{
int to=edge[i].to;
if(to==pre) continue;
DP(to,source);
for(int j=K;j>=;j--)
{
dp[source][j]+=dp[to][]+*edge[i].value;
for(int k=;k<=j;k++)
dp[source][j]=MIN(dp[source][j],dp[source][j-k]+dp[to][k]+k*edge[i].value);
}
}
} int main()
{
while(scanf("%d %d %d",&N,&S,&K)!=EOF)
{
memset(dp,,sizeof(dp));
memset(head,-,sizeof(head));
total=; int x,y,cost;
for(int i=;i<N;i++)
{
scanf("%d %d %d",&x,&y,&cost);
addEdge(x,y,cost);
}
DP(S,-);
printf("%d\n",dp[S][K]);
}
return ;
}
思路和其他人差不多，谈谈自己是怎么理解的吧：
首先，用两数组建立无向树，还是第一次，费了不少功夫。定义一个结构代表边edge[i]={to,next,value},其中edge[i]表示第i条边，to是边的末点，value就不说了，next代表的是同一父节点边方向相同的与此边相邻的左边的边的编号，其中最左是-1。以此为基础建立一个边数组（注意数组大小是顶点数的两倍），还有用一个head[i]数组来表示最右边的边的编号。
解释这一段代码，当时写的理解的不是很好：
void DP(int source,int pre)
{
for(int i=head[source];i!=-;i=edge[i].next)
{
int to=edge[i].to;
if(to==pre) continue;
DP(to,source);
for(int j=K;j>=;j--)
{
dp[source][j]+=dp[to][]+*edge[i].value;
for(int k=;k<=j;k++)
dp[source][j]=MIN(dp[source][j],dp[source][j-k]+dp[to][k]+k*edge[i].value);
}
}
}
第一层for循环查找与节点source相连的各条边，to是此边对应的末点，若此边是叶子节点则to==pre（由于节点最左边的边访问完以后，只有到他父节点的边，这里只能用continue，因为不确定访问的顺序，return不合适）,递归访问子节点此时应用01背包，由于dp[source][0]比较特殊单独处理，一棵子树对应一个分组，dp[source][j]=MIN(dp[source][j],dp[source][j-k]+dp[to][k]+k*edge[i].value);也比较好理解。