【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：

2

题解

树型DP

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

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

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

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 300

inline 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<n;++i)

	{

		int u=read(),v=read();

		Add(u,v);Add(v,u);

	}

	memset(f,63,sizeof(f));

	DFS(1,0);

	cout<<ans<<endl;

	return 0;

}