【题解】洛谷 P3942 将军令【20201017 CSP 模拟赛】【贪心】

题目链接

题目链接

题意

在树中选择尽可能少的关键点以覆盖所有点，每个关键点能覆盖与之距离不超过 (k) 的点。(kleq 20)，(nleq 10^5)（实际可以做 (O(n))）。

题解

考场上写的 (O(nk^2)) 的 DP，但实际上可以贪心做到 (O(n))。

DP 做法：考虑 (f[i,j]) 表示 (i) 及其子树被完全覆盖，且覆盖的范围还能再向上延伸 (j)；(g[i,j]) 表示 (i) 及其子树未被完全覆盖，最深的一个未被完全覆盖的一个相对 (i) 的深度为 (j)。

贪心做法：每次考虑最深的一个点，覆盖它的点肯定是取它的 (k) 代祖先最优。在 DFS 时处理可以做到 (O(n))

代码（DP）：

#include<bits/stdc++.h>
using namespace std;
int getint(){
	int ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*f;
}
const int N=1e5+10,K=23;
struct bian{
	int e,n;
};
bian b[N<<1];
int s[N],tot=0;
void add(int x,int y){
	tot++;
	b[tot].e=y;
	b[tot].n=s[x];
	s[x]=tot;
}
int n,m,T;
int f[N][K],g[N][K],tmp[K],pmt[K];
void ss(int x,int fa){
	memset(f[x],0x3f,sizeof(f[x]));
	memset(g[x],0x3f,sizeof(g[x]));
	f[x][m]=1;
	g[x][0]=0;
	for(int i=s[x];i;i=b[i].n){
		int v=b[i].e;
		if(v==fa)continue;
		ss(v,x);
		memset(tmp,0x3f,sizeof(tmp));
		memset(pmt,0x3f,sizeof(pmt));
		for(int j=0;j<=m;j++){ // f
			// from f[x][j]
			for(int k=0;k<=j+1;k++)tmp[j]=min(tmp[j],f[x][j]+f[v][k]);
			for(int k=0;k<=j-1;k++)tmp[j]=min(tmp[j],f[x][j]+g[v][k]);
			// from f[v][j+1]
			for(int k=0;k<=j;k++)tmp[j]=min(tmp[j],f[v][j+1]+f[x][k]);
			for(int k=0;k<=j;k++)tmp[j]=min(tmp[j],f[v][j+1]+g[x][k]);
		}
		for(int j=0;j<=m;j++){ // g
			// from g[x][j]
			for(int k=0;k<=j-1;k++)pmt[j]=min(pmt[j],g[x][j]+g[v][k]);
			for(int k=0;k<=j  ;k++)pmt[j]=min(pmt[j],g[x][j]+f[v][k]);
			// from g[v][j-1]
			if(!j)continue;
			for(int k=0;k<=j  ;k++)pmt[j]=min(pmt[j],g[v][j-1]+g[x][k]);
			for(int k=0;k<=j-1;k++)pmt[j]=min(pmt[j],g[v][j-1]+f[x][k]);
		}
		memcpy(f[x],tmp,sizeof(f[x]));
		memcpy(g[x],pmt,sizeof(g[x]));
	}
//	cerr<<"f "<<x<<" : ";for(int i=0;i<=m;i++)cerr<<f[x][i]<<" ";cerr<<endl;
//	cerr<<"g "<<x<<" : ";for(int i=0;i<=m;i++)cerr<<g[x][i]<<" ";cerr<<endl;
}

int main(){
	n=getint(),m=getint(),T=getint();
	for(int i=1;i<n;i++){
		int x=getint(),y=getint();
		add(x,y);
		add(y,x);
	}
	ss(1,0);
	int ans=0x7f7f7f7f;
	for(int i=0;i<=m;i++)ans=min(ans,f[1][i]);
	cout<<ans;
}