题目描述
农夫John的农场有n（n<=150）个牛舍，有些牛舍之间有双向道路连接，而每两个牛舍之间有且仅有一条道路（因此可以表示成一棵树）。由于任意一场地震都很可能让John的农场变得不连通，因此John希望估计一下，至少需要毁坏多少条道路才会让一个恰好有p（p<=n）个牛舍的子树脱离其他牛舍。
此题采用树型动态规划求解。
1、建树
由于一个结点可能会有多个子结点，给下面的动态规划带来不便，所以采用“左儿子右兄弟”表示法。
2、状态定义
定义d(i,j)表示在i结点上选取它的儿子或右边的兄弟或右边的兄弟的兄弟……共j个（包含自身）至少需要毁坏的道路数。
3、状态转移方程
考虑几种决策：
i结点连同所有儿子结点都舍弃不用：d(i,j)=d(R(i),j)+1；
i结点由包含k个结点的左子树和j-k-1个结点的右子树组成：d(i,j)=d(L(i),k)+d(R(i),j-k-1)；
4、边界条件
为了方便处理，如果一个结点没有左儿子或右儿子（在转换之后的二叉树中），那么它的左儿子或右儿子为0号结点。
那么边界可以是：
d(0,0)=0；
d(0,i)=INF,1<=i<=n；
我觉得这种表示还是很巧妙的。
注意，即使以i结点为根的数左子树为空，也不一定毁坏一条道路就能剪掉整个左子树，因为这是转换了之后的二叉树，原树上i结点可能有众多子结点。
5、最优解
在d(L(i),p-1)+(i==root?0:1)中找最优解。因为如果i是根节点，不需要毁坏任何道路。
以下是我的代码：
#include<fstream>
#include<string.h>
#define maxn 157
#define INF 20000007
using namespace std;
long min(long a,long b){return (a<b?a:b);}
typedef struct
{
long ls,rs;
}treenode;
long n,p,root,ans,father[maxn],d[maxn][maxn];
treenode tree[maxn];
void Insert(long u,long v)
{
if(!tree[u].ls)
tree[u].ls=v;
else
{
long p;
for(p=tree[u].ls;tree[p].rs;p=tree[p].rs);
tree[p].rs=v;
}
}
long dp(long i,long j)
{
if(d[i][j]!=-1) return d[i][j];
d[i][j]=dp(tree[i].rs,j)+1;
for(long k=0;j-k-1>=0;k++)
d[i][j]=min(d[i][j],dp(tree[i].ls,k)+dp(tree[i].rs,j-k-1));
return d[i][j];
}
int main()
{
ifstream fin("roads.in");ofstream fout("roads.out");
memset(tree,0,sizeof(tree));
memset(father,0,sizeof(father));
fin>>n>>p;
for(long i=1;i<=n-1;i++)
{
long u,v;
fin>>u>>v;
Insert(u,v);
father[v]=u;
}
// Input
memset(d,-1,sizeof(d));
for(long i=1;i<=n;i++)
d[0][i]=INF;
d[0][0]=0;
// Init
for(long i=1;i<=n;i++)
if(!father[i])
root=i;
// Find root
ans=INF;
for(long i=1;i<=n;i++)
ans=min(ans,dp(tree[i].ls,p-1)+(i==root?0:1));
fout<<ans<<endl;
// Output
fin.close();fout.close();
return 0;
}
posted on 2010-10-11 22:47
lee1r 阅读(549)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划