洛谷P1272 重建道路 题解

洛谷P1272 重建道路 题解

题目链接：P1272 重建道路

题意：

一场可怕的地震后，人们用 N N N 个牲口棚（编号 1 ∼ N 1\sim N 1∼N）重建了农夫 John 的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。

John 想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有 P P P 个牲口棚的子树和剩余的牲口棚分离，John 想知道这些道路的最小数目。

1 ≤ N ≤ 150 1\le N\le 150 1≤N≤150， 1 ≤ P ≤ N 1\le P\le N 1≤P≤N，保证给出的是一棵树。

题目有点难懂，意思就是说切最少刀切出一个大小为 p p p 的块，显然树上背包

设 d p [ u ] [ j ] dp[u][j] dp[u][j] 表示 u u u 所在子树切出大小为 j j j 的块并强制包含 u u u 的最小花费，则
d p [ u ] [ j + k ] = min ⁡ ( d p [ u ] [ j + k ] , tmp [ j ] + d p [ v ] [ k ] − 1 ) dp[u][j+k]=\min(dp[u][j+k],\text{tmp}[j]+dp[v][k]-1) dp[u][j+k]=min(dp[u][j+k],tmp[j]+dp[v][k]−1)
其中 tmp [ j ] \text{tmp}[j] tmp[j] 为上一轮的 d p [ u ] [ j ] dp[u][j] dp[u][j] 。

后面一个柿子比较难懂

考虑一个大小为 j j j 的块（包含 u u u ）和一个大小为 k k k 的块（包含 v v v ）合并，显然要把和 v v v 相连的那条边连上，但是本来是算在里面的（虽然是在最后才算的）

解释可能不是很清楚，直接看代码好了，细节比较多的

这道题的题解真是误导大众，填表法的树上背包是假的啊！

所有sz在dp前加的都是假复杂度。别怪我没提醒你们哦

时间复杂度 O ( n p ) O(np) O(np)

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(205)

int n,p;
int tmp[N],sz[N],dp[N][N];
vector<int> vec[N];
void dfs(int u,int f)
{
    sz[u]=1;dp[u][1]=0;
    for(int v : vec[u])
        if(v!=f)++dp[u][1];
    for(int v : vec[u])
    {
        if(v==f)continue;
        dfs(v,u);
        for(int j=0; j<=min(sz[u],p); j++)
            tmp[j]=dp[u][j];
        for(int j=1; j<=min(sz[u],p); j++)
            for(int k=1; k<=min(sz[v],p)&&j+k<=p; k++)
                dp[u][j+k]=min(dp[u][j+k],tmp[j]+dp[v][k]-1);
        sz[u]+=sz[v];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> p;
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    memset(dp,0x3f,sizeof(dp));
    dfs(1,1);int res=dp[1][p];
    for(int i=2; i<=n; i++)
        res=min(res,dp[i][p]+1);
    cout << res << '\n';
    return 0;
}

转载请说明出处