[Usaco2002 Feb]Rebuilding Roads重建道路

题目

Description

一场可怕的地震后,奶牛用N个牲口棚(1 <= N <= 150,编号1..N)重建了农民John的牧场。奶牛没有时间建设多余的道路,所以现在从一个牲口棚到另一个牲口棚的道路是唯一的。因此,牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏,就会使一棵含有P(1 <= P <= N)个牲口棚的子树和剩余子牲口棚分离,John想知道这些道路的最小数目。

Input

* 第1行:2个整数, N和P
* 第2..N行:每行2个整数I和J,表示节点I是节点J的父节点。

Output

单独一行,包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。

Sample Input

11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11

Sample Output

2

Hint

[如果道路1-4和1-5 被破坏,含有节点(1, 2, 3, 6, 7, 8) 的子树将被分离出来] 

思路

这是一道树形dp的题;

我们设dp[x][i]表示以x为根保留i个节点需要割掉多少边;

那么如果x使叶子节点的话,dp[x][1]=1;(保留这个叶子节点,需要割去上面与它相连的父节点);

然后,我们会发现,每个节点与它相连的就是它的父节点与它的子节点;

那么dp[x][1]=子节点数+1;割去所有与它相连的边就可以保留x这个点;

但是根节点上面使没有父节点与它相连,所以dp[1][1]=子节点数;

dp方程是:

dp[x][i]=min(dp[x][i],dp[xx][j]+dp[x][i-j]-2);

xx是x的son,j枚举儿子节点割去的边数

为什么要减二呢,在初始dp[x][1]时割去了x与xx相连的边,初始dp[xx][1]时也割去了这条边;

所以转移的时候要减二;

 

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read()
{
    ll a=0,f=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
    return a*f;
}
ll n,q;
ll head[2010],dp[2010][2100],son[2010],v[2010],dep[2010];
struct ljj
{
    ll stb,to;
}a[2010];
ll s=0;
inline void insert(ll x,ll y)//连边
{
    s++;
    a[s].stb=head[x];
    a[s].to=y;
    head[x]=s;
}
inline void dfs(ll x,ll fa)//遍历
{
    for(ll i=head[x];i;i=a[i].stb)
    {
        ll xx=a[i].to;
        if(xx==fa)
            continue;
        dfs(xx,x);
        for(ll j=q;j>=0;j--)
        for(ll k=0;k<=j;k++)
            dp[x][j]=min(dp[x][j],dp[xx][k]-1+dp[x][j-k]-1);
//在初始dp[x][1]时割去了x与xx相连的边,初始dp[xx][1]时也割去了这条边; //所以转移的时候要减二; // cout<<x<<" "<<j<<" "<<k<<" "<<dp[x][j]<<" "<<dp[xx][k]<<" "<<dp[x][j-k]<<endl; } } int main() {//具体解析看思路 memset(dp,127/3,sizeof(dp));//因为题目求最小值,如果不把数组设为无限大,答案就会是0 n=read();q=read(); for(ll i=1;i<n;i++) { ll x=read(),y=read(); insert(x,y); insert(y,x); son[x]++;//统计每个节点的子节点 } for(ll i=1;i<=n;i++) dp[i][1]=son[i]+1; dp[1][1]=son[1];//根节点上面使没有父节点与它相连,所以dp[1][1]=子节点数; dfs(1,0); ll ans=1<<30; for(ll i=1;i<=n;i++) ans=min(ans,dp[i][q]); printf("%lld\n",ans); }

 

上一篇:如何为 QT5 装上 QT4 才有的库


下一篇:linux的shell命令源码在哪能找到?比如find的源码