【Luogu1272】重建道路（动态规划）

题面

题目描述

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

输入输出格式

输入格式：

第1行：2个整数，N和P

第2..N行：每行2个整数I和J，表示节点I是节点J的父节点。

输出格式：

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

输入输出样例

输入样例#1：

11 6

1 2

1 3

1 4

1 5

2 6

2 7

2 8

4 9

4 10

4 11

输出样例#1：

题解

树型DP

设\(f[i][j]\)表示当前以\(i\)为根节点，保留\(j\)个节点的最小代价

转移有所有子树的值转移过来

其中\(f[i][1]=degree[i]\)，其中\(degree\)表示出度

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define MAX 300inline int read(){ int x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}struct Line{ int v,next;}e[MAX<<1];int lk[MAX];int h[MAX],cnt=1;int size[MAX],n,p,ans=1e9;inline void Add(int u,int v){ e[cnt]=(Line){v,h[u]}; h[u]=cnt++;lk[u]++;}int f[MAX][MAX];void DFS(int u,int ff){ size[u]=1;f[u][1]=lk[u]-(ff!=0); for(int i=h[u];i;i=e[i].next) { int v=e[i].v; if(v==ff)continue; DFS(v,u); for(int j=p;j;--j) for(int k=1;k<=j;++k) f[u][j]=min(f[u][j],f[v][k]+f[u][j-k]-1); } ans=min(ans,f[u][p]+(ff!=0));}int main(){ n=read();p=read(); for(int i=1;i

转载于:https://www.cnblogs.com/cjyyb/p/7806030.html

你可能感兴趣的文章