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

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

2024-07-04 10:54:52   227人阅读

善良的国王

时间限制：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;
}


联系
我们