这是一个孩子之间有分配的树形动态规划问题，一般解决的方法为左孩子右兄弟法或孩子背包分配。
左孩子右兄弟表示法中，状态设定为
F[i,j]表示以i为根的子树以及以i右边兄弟为根的子树中选j个点需要删除边的最少数量。F[i,j]还隐含了i的父亲已经被选，否则i是不可能被选的。
状态转移方程为
F[i][j] = Min { F[i.brother][j] + 1 (不选节点i) F[i.child][k] + F[i.brother][j-k-1] (选节点i) 0<=k<=i子树及兄弟子树大小-1 且 k<=j-1 }
边界条件
F[i][0] = F[i.brother][0] + 1 节点0为一个虚构的节点，如果节点i没有兄弟(或儿子)，则它的兄弟(或儿子)为0。 F[0][0]=0 F[0][j]=INF (j>0，INF为一个极大的值)
目标状态
左孩子右兄弟表示法的目标状态表示不很直观，一棵子树分配P个节点，需要表示成子树根第一个孩子及其兄弟分配P-1的节点。另外，如果不是根节点，还要增加1，表示与它的父节点的边也断掉。 Ans = Min{ F[根节点的第一个孩子][P-1] , F[非根节点的第一个孩子][P-1] + 1 }
如果用孩子背包分配法，状态可以表示为
F[i][j]为以i为根的子树中选择j个节点要删除边的最少数量。
状态转移方程为
F[i][j] = Min { Sigma{ F[i.child[k]][m[k]] } } 其中 sigma[m[k]] = j-1 直接在孩子中分配不易，需要再进行一次DP，运用背包的思想，设状态
G[a][b]为对于特定的i时i的前i个孩子分配j个节点的最小值
G[a][b] = Min { G[a-1][b-k] + F[i.child[a]][k] }
于是F[i][j]可以表示为 F[i][j] = G[i.childcount][j-1]
边界条件为
对于每个节点i G[0][0]=0 G[0][j]=INF (j>0 INF为一个极大的值)
当i为叶节点时 F[i][0]=1 F[i][1]=0
目标状态
Ans = Min{ F[根节点][P] , F[非根节点][P] + 1}
对于这道题，两种方法的时间复杂度均为O(N^3)。左孩子右兄弟法的优点在于状态转移比较简单，缺点是不够直观，尤其在表示目标状态的时候，另外边界情况的考虑也比较复杂，还有就是需要额外建树。孩子背包分配的方法优点是状态直观，易于表示，容易写成非递归，缺点是状态转移较为复杂，需要用一个背包再分配一次。我个人比较倾向于孩子背包分配法，除非必须，我一般都会写成这样的。
左孩子右兄弟
/*
* Problem: pku1947 Rebuilding Roads
* Author: Guo Jiabao
* Time: 2009.6.11 8:44
* State: Solved
* Memo: 树形动态规划 孩子兄弟
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=151,INF=0x7FFFFFF;
struct edge
{
edge *next;
int t;
}ES[MAXN*2],*V[MAXN];
struct TreeNode
{
int child,brother,size;
}P[MAXN];
int N,K,EC,Ans,F[MAXN][MAXN];
inline void addedge(int a,int b)
{
ES[++EC].next = V[a];
V[a]=ES+EC; V[a]->t=b;
}
void buildtree(int i,int f)
{
for (edge *e=V[i];e;e=e->next)
{
int j=e->t;
if (j==f) continue;
P[j].brother = P[i].child;
P[i].child = j;
buildtree(j,i);
}
}
void calcsize(int i)
{
if (i==0) return;
calcsize(P[i].brother);
calcsize(P[i].child);
P[i].size = P[ P[i].brother ].size + P[ P[i].child ].size + 1;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
void init()
{
int i,a,b;
freopen("rr.in","r",stdin);
freopen("rr.out","w",stdout);
scanf("%d%d",&N,&K);
for (i=1;i<N;i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
buildtree(1,0);
calcsize(1);
memset(F,-1,sizeof(F));
}
int dp(int i,int j)
{
int rs = F[i][j];
if (rs==-1)
{
if (i==0)
{
if (j==0)
rs = 0;
else
rs = INF;
}
else if (j==0)
rs = dp(P[i].brother,0) + 1;
else
{
rs = INF;
rs = min(rs,dp(P[i].brother,j) + 1);
for (int k=0;k<=P[i].size-1 && k<=j-1;k++)
rs = min(rs,dp(P[i].child,k) + dp(P[i].brother,j-k-1));
}
F[i][j]=rs;
}
return rs;
}
void solve()
{
int i;
if (N==1)
Ans = 0;
else if (K==1)
Ans = 1;
else
{
Ans = dp(P[1].child,K-1);
for (i=2;i<=N;i++)
if (P[i].child)
Ans = min(Ans,dp(P[i].child,K-1) + 1);
}
}
int main()
{
init();
solve();
printf("%dn",Ans);
return 0;
}
孩子背包分配
/*
* Problem: pku1947 Rebuilding Roads
* Author: Guo Jiabao
* Time: 2009.6.11 10:04
* State: Solved
* Memo: 树形动态规划 孩子链+背包
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=151,INF=0x7FFFFFF;
struct edge
{
edge *next;
int t;
}ES[MAXN*2],*V[MAXN];
int N,K,EC,Ans,F[MAXN][MAXN],G[MAXN],Size[MAXN],A;
inline void addedge(int a,int b)
{
ES[++EC].next = V[a];
V[a]=ES+EC; V[a]->t=b;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
void init()
{
int i,j,a,b;
freopen("rr.in","r",stdin);
freopen("rr.out","w",stdout);
scanf("%d%d",&N,&K);
for (i=1;i<N;i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
for (i=1;i<=N;i++)
for (j=1;j<=N;j++)
F[i][j]=INF;
}
void dp(int i,int f)
{
int j,k;
edge *e;
Size[i]=1;
for (e=V[i];e;e=e->next)
{
j=e->t;
if (j==f) continue;
dp(j,i);
Size[i] += Size[j];
}
if (Size[i]==1)
{
F[i][0]=1;
F[i][1]=0;
}
else
{
for (j=1;j<=Size[i]-1;j++)
G[j]=INF;
G[0]=0;
for (e=V[i];e;e=e->next)
{
if (e->t==f) continue;
for (j=Size[i]-1;j>=0;j--)
{
A=INF;
for (k=0;k<=Size[e->t] && k<=j;k++)
{
A=min(A,G[j-k] + F[e->t][k]);
}
G[j]=A;
}
}
F[i][0]=1;
for (j=1;j<=Size[i];j++)
{
F[i][j] = G[j-1];
}
}
}
void solve()
{
int i;
dp(1,0);
Ans = F[1][K];
for (i=2;i<=N;i++)
Ans = min(Ans,F[i][K]+1);
}
int main()
{
init();
solve();
printf("%dn",Ans);
return 0;
}
上次修改时间 2017-02-03