首页 > 代码库 > NYOJ 674 善良的国王(树形背包DP)

NYOJ 674 善良的国王(树形背包DP)

善良的国王

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
描述
传说中有一个善良的国王Good,他为了不劳民伤财,每当建造一个城镇的时候都只用一条路去连接,这样就可以省很多的人力和物力,也就说如果有n个城镇,那么只需要n-1条路就可以把所有的城镇链接起来了(也就是一颗树了)。但是不幸的事情发生了:有个一强大的帝国想要占领这个国家,但是由于国王Good的兵力不足,只能守护m个城镇,所以经过商量,国王Good只能从他的所有城镇中选择m个相链接的城市,并且把所有可以链接到这m个城镇的道路都毁掉以阻止强大帝国的入侵。由于毁掉道路也需要花费一定的代价,所以为了经可能的保存实力,国王Good想要毁掉最可能少的道路。现在请聪明的你帮助这位善良的国王Good吧。(m个城市可以是任意的,只要能连接在一起就可以。
输入
第一行一个t,代表有t组测试数据;
每组测试数据第一行有两个数,n,m(0<n<500,0=<m<=n)分别代表城镇总的数量和要保留的城镇数量。
接下来的n-1行,每行包括两个数字,x,y(0<x,y<=n)表示x和y连通。
输出
每组输出站一行。输出格式“case #i: ans”,i代表第i组测试数据,ans即为最少要删除的边数。
样例输入
1
10 3
1 5
1 6
1 7
7 8
7 9
7 10
6 3
6 4
3 2
样例输出
case #1: 2
树形动态规划!   同http://poj.org/problem?id=1947
AC码:
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define M 500
#define INF 9999999
vector<int> adj[M];
int f[M][M],vex[M];
int n,p,ans;
int min(int a,int b)
{
	return a>b?b:a;
}
int DP(int u)
{
	vex[u]=1;
	int i,j,k,v,len=adj[u].size();
	for(i=0;i<len;i++)
	{
		v=adj[u][i];
		vex[u]+=DP(v);
	}
	f[u][1]=len;
	for(i=0;i<len;i++)
	{
		v=adj[u][i];
		for(k=vex[u];k>=1;k--)
		{
			for(j=1;(j<k)&&(j<=vex[v]);j++)
				f[u][k]=min(f[u][k],f[u][k-j]+f[v][j]-1);
		}
	}
	if(vex[u]>=p)
		ans=min(ans,f[u][p]+(u!=1));
	return vex[u];
}
int main()
{
	int T,i,a,b,count=1;
	scanf("%d",&T);
	while(T--)
	{
		for(i=0;i<M;i++)
			adj[i].clear();
		scanf("%d%d",&n,&p);
		for(i=0;i<n-1;i++)
		{
			scanf("%d%d",&a,&b);
			adj[a].push_back(b);
		}
		ans=INF;
		memset(f,INF,sizeof(f));
		DP(1);
		printf("case #%d: %d\n",count++,ans);
	}
	return 0;
}

重建道路
时间限制: 1000MS 内存限制: 30000K
总提交: 8780 接受日期: 3954

描述

奶牛已在可怕的地震去年五月后重建农夫约翰的农场,与它的N谷仓(1 <= N <= 150,数字1 .. N)。牛没有时间来重建任何额外的道路,所以现在正是从任何给定的谷仓去任何其他谷仓的一种方式。因此,养殖场运输系统可以表示为一棵树。 农夫约翰想要知道另一地震可能造成的伤害。他想知道道路的最小数量,其破坏将隔离正好P(1 <= P <= N)从谷仓的其余部分谷仓的一个子树。

输入

*第1行:两个整数N和P *第2 .. N:N-1行,每 ??行有两个整数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
AC码:
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define M 500
#define INF 9999999
vector<int> adj[M];
int f[M][M],vex[M];
int n,p,ans;
int min(int a,int b)
{
	return a>b?b:a;
}
int DP(int u)
{
	vex[u]=1;
	int i,j,k,v,len=adj[u].size();
	for(i=0;i<len;i++)
	{
		v=adj[u][i];
		vex[u]+=DP(v);
	}
	f[u][1]=len;
	for(i=0;i<len;i++)
	{
		v=adj[u][i];
		for(k=vex[u];k>=1;k--)
		{
			for(j=1;(j<k)&&(j<=vex[v]);j++)
				f[u][k]=min(f[u][k],f[u][k-j]+f[v][j]-1);
		}
	}
	if(vex[u]>=p)
		ans=min(ans,f[u][p]+(u!=1));
	return vex[u];
}
int main()
{
	int i,a,b;
	scanf("%d",&T);
	for(i=0;i<M;i++)
		adj[i].clear();
	scanf("%d%d",&n,&p);
	for(i=0;i<n-1;i++)
	{
		scanf("%d%d",&a,&b);
		adj[a].push_back(b);
	}
	ans=INF;
	memset(f,INF,sizeof(f));
	DP(1);
	printf("%d\n",ans);
	return 0;
}