USACO 2002 February Green 重建道路

54 阅读 0 评论 36 点赞

我是靠谱客的博主独特茉莉，最近开发中收集的这篇文章主要介绍USACO 2002 February Green 重建道路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

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

Input

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

Output

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

Sample Input

11 6

1 2

1 3

1 4

1 5

2 6

2 7

2 8

4 9

4 10

4 11

Sample Output

题目大意：给定一棵无根树，要求断最少的边得到一棵大小为m的子树。

首先容易想到f[p][i][j]表示以i为根的前p棵子树大小为j最少需要的断边数，f[0][i][1]=出度+入度

那么有：f[p][i][j]=max{f[p-1][i][j-k]+g[to][k]-2}，发现有点不好写。。。又发现和背包很像。。。仔细看发现都是迭代着走的，容易想到01背包的模型，得到：f[i][j]=max{f[i][j-k]+f[i][k]-2}，为什么-2呢？因为计算时二者是不连通的to减了1，i减了1，但又要保证是连通的，所以要加回去。

虽然是无根树，但随便找一个当根dp是等价的A.<

#include<bits/stdc++.h>
using namespace std;
#define Inc(i,L,r) for(register int i=(L);i<=(r);++i)
const int N = 233;
struct Edge{
	int cnt,h[N],to[N<<1],next[N<<1];
	inline void add(int x,int y){
		next[++cnt]=h[x];
		to[cnt]=y;
		h[x]=cnt;
	}
}e;
int n,m,rt,p[N];
int f[N][N];//以i为根，大小为j的子树最少断边
void init(){
	scanf("%d%d",&n,&m);
	Inc(i,1,n-1){
		int x,y;scanf("%d%d",&x,&y);
		e.add(x,y),e.add(y,x);
		p[y]=x;
	}
	Inc(i,1,n)if(!p[i])rt=i;
	memset(f,63,sizeof(f));
}
void trdp(int x,int fa){
	f[x][1]=0;
	for(int p=e.h[x];p;p=e.next[p])++f[x][1];
	
	for(int p=e.h[x];p;p=e.next[p]){
		int to=e.to[p];
		if(to==fa)continue;
		trdp(to,x);
		for(int j=m;j>1;--j){
			Inc(k,1,j-1)if(f[to][k]<=n){
				f[x][j]=min(f[x][j],f[to][k]+f[x][j-k]-2);
			}
		}
	}
}
int main(){
	init();
	trdp(rt,0);
	int ans=1<<30;
	Inc(i,1,n)ans=min(ans,f[i][m]);
	cout<<ans<<"n";
	return 0;
}