【赛前复习】树形DP

前言:

没有,下一个

学习博客:

简单介绍:

题目

Fire

Fire

给定一棵树,对于任意节点 \(i\) 需要满足至少一个条件。
1.可以花费一定代价 \(w_i\) 建消防站;
2.离它最近的消防站的之间的距离不超过 \(D_i\),
求满足条件的最小花费。

\(dp_{i, j}\): 表示城市 \(i\) 的负责点是 \(j\) 的情况。

再来一个数组 \(g_i\) 表示 \(i\) 的子树内负责点不定的最小代价

\(dp_{i, j}\) 向上传递,由儿子传递到父亲。

对于一棵树来说,父亲为 \(x\), 儿子为 \(y\)。

  • 如果 \(x\), \(y\) 由同一个节点 \(a\) 负责,

\(dp_{x, a} += dp_{y,a} - w_a\);

直接减去重复计算的 \(w_a\) 即可

  • 如果x, y 不由同一个节点负责,那就不用管 y 具体由哪个节点负责,直接用 \(g_y\) 转移

\(dp_{x,a} += g_y\)

关于 \(g_x\) 的转移就是,每次枚举 负责 \(x\) 的节点 \(i\) , 处理完后,取最小值

\(g_x = \min\) { \(dp_{x,i}\) } \((dis_{x, i} <= D_x)\)


#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1005;
int t, n, D[N], W[N], tot, head[N], nex[N << 1], to[N << 1], w[N << 1], dis[N][N];
void add(int x, int y, int z) {
	to[++tot] = y, nex[tot] = head[x], head[x] = tot, w[tot] = z; 
}
void dfs(int st, int x, int f) {
	int ver;
	for(int i = head[x]; i; i = nex[i]) {
		ver = to[i];
		if(ver == f) continue;
		dis[st][ver] = dis[st][x] + w[i];
		dfs(st, ver, x);
	}
}
int dp[N][N], g[N];
void solve(int x, int f) {
	int ver;
	for(int i = head[x]; i; i = nex[i]) {
		ver = to[i];
		if(ver == f) continue;
		solve(ver, x);
	}
	for(int i = 1; i <= n; i ++) {
		if(dis[i][x] > D[x]) continue;
		dp[x][i] = W[i];
		for(int j = head[x]; j; j = nex[j]) {
			ver = to[j];
			if(ver == f) continue;
			dp[x][i] += min(dp[ver][i] - W[i], g[ver]);
		} 
		g[x] = min(g[x], dp[x][i]);
	}
}

int main() {
	int u, v, ww;
	scanf("%d", &t);
	while(t --) {
		scanf("%d", &n);
		tot = 0;
		memset(head, 0, sizeof(head));
		memset(dp, 0x3f, sizeof(dp));
		memset(g, 0x3f, sizeof(g));
		for(int i = 1; i <= n; i ++) scanf("%d", &W[i]);
		for(int i = 1; i <= n; i ++) scanf("%d", &D[i]);
		for(int i = 1; i < n; i ++) {
			scanf("%d %d %d", &u, &v, &ww);
			add(u, v, ww), add(v, u, ww);
		}
		for(int i = 1; i <= n; i ++) {
			dis[i][i] = 0;
			dfs(i, i, 0);
		}
		solve(1, 0);
		printf("%d\n", g[1]);
	}
	
	return 0;
}

Rebuilding Roads

Rebuilding Roads
or
Luogu重建道路

给定一棵 n 个节点的树,问最少删去多少条边,能够得到一个节点个数为 p 的连通块。

\(dp_{i,j}\) 表示 以 \(i\) 为根的子树 保留 \(j\) 个点联通的最小代价

重点在 \(dp\) 的初始条件的设置。

以及式子的小细节处理

$ dp_{i, j} = min(dp_{i, j}, dp_{i, j - k} + dp_{ver, k} - 1) $

因为 \(x\) 和 \(ver\) 之间相连是存在一条边的, 而那条边没有算进 \(dp_{ver, k}\) 中, 可能会在 \(dp_{x, j - k}\) 中被当成删边, 所以要 -1

初始值的设置真的好妙

最后答案统计也要注意,因为除树根之外的点在 \(DP\) 时都没有考虑 父亲, 所以最后还要额外删去 和父亲相连的那条边



#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 155;
int n, p, rt, ans = 1e9, fa[N], tot, head[N], nex[N], to[N], dp[N][N], in[N], out[N];

void add(int x, int y) {
	to[++tot] = y, nex[tot] = head[x], head[x] = tot;
}
int siz[N];
void dfs(int x) {
	int ver;
	siz[x] = 1;
	for(int i = head[x]; i; i = nex[i]) {
		ver = to[i];
		dfs(ver);
		siz[x] += siz[ver];
	}
	for(int i = head[x]; i; i = nex[i]) {
		ver = to[i];
		for(int j = siz[x]; j; j --) {
			for(int k = 1; k < j; k ++) {
				dp[x][j] = min(dp[x][j], dp[x][j - k] + dp[ver][k] - 1);
			}
		}
	}
}

int main() {
	int u, v;
	memset(dp, 0x3f, sizeof(dp));
	scanf("%d %d", &n, &p);
	for(int i = 1; i < n; i ++) {
		scanf("%d %d", &u, &v);
		out[u] ++, in[v] ++;
		add(u, v);
	}
	for(int i = 1; i <= n; i ++) {
		if(!in[i]) rt = i;
		dp[i][1] = out[i];
	} 
	dfs(rt);
	ans = dp[rt][p];
	for(int i = 1; i <= n; i ++) ans = min(ans, dp[i][p] + 1);
	printf("%d", ans);
	return 0;
} 


Road Improvement

上一篇:最短路


下一篇:B. Complete The Graph(最短路算法)