題目描述
農夫John的農場有n（n<=150）個牛舍，有些牛舍之間有雙向道路連接，而每兩個牛舍之間有且僅有一條道路（因此可以表示成一棵樹）。由于任意一場地震都很可能讓John的農場變得不連通，因此John希望估計一下，至少需要毀壞多少條道路才會讓一個恰好有p（p<=n）個牛舍的子樹脫離其他牛舍。
此題采用樹型動態(tài)規(guī)劃求解。
1、建樹
由于一個結點可能會有多個子結點，給下面的動態(tài)規(guī)劃帶來不便，所以采用“左兒子右兄弟”表示法。
2、狀態(tài)定義
定義d(i,j)表示在i結點上選取它的兒子或右邊的兄弟或右邊的兄弟的兄弟……共j個（包含自身）至少需要毀壞的道路數(shù)。
3、狀態(tài)轉移方程
考慮幾種決策：
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結點為根的數(shù)左子樹為空，也不一定毀壞一條道路就能剪掉整個左子樹，因為這是轉換了之后的二叉樹，原樹上i結點可能有眾多子結點。
5、最優(yōu)解
在d(L(i),p-1)+(i==root?0:1)中找最優(yōu)解。因為如果i是根節(jié)點，不需要毀壞任何道路。
以下是我的代碼：
#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 閱讀(595)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃