游客 注册 | 登录
中文 | En

3769 - 道路

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

 一场可怕的地震后，人们用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个节点的子树的道路的最小数目。

输入/输出样例

输入格式

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

输出格式

2

C++解答

/*====================
AUTHOR:MOSHANGYIN
TYPE:TREE DP
TITLE:REBUILD ROADS
====================*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector<int> g[155];
int n,p,x,y,id[155]={0};
int f[155][155]={0};
inline int in()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')
	{
	 	c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar())
	{
	 	x=x*10+c-'0';
	}
	return x;
}
void dp(int x)
{
	f[x][1]=0;
	for(int i=0;i<g[x].size();i++)
	{
		dp(g[x][i]);
		for(int j=p;j>=1;j--)
		{
			f[x][j]++;
			for(int k=1;k<j;k++)
			{
				f[x][j]=min(f[x][j],f[g[x][i]][j-k]+f[x][k]);
			}
		}
	}
}
int main()
{
	n=in(),p=in();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=p;j++)
		{
			f[i][j]=100001;
		}
	} 
	for(int i=1;i<n;i++)
	{
		x=in(),y=in();
		id[y]++;
		g[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		if(id[i]==0)
		{
			dp(i);
			int ans=f[i][p];
			for(int i=1;i<=n;i++)
			{
				ans=min(ans,f[i][p]+1); 
			}
			printf("%d\n",ans);
			break;
		}
	}
	return 0;
}
请先登陆