您的位置: 首页  >  IT文章  >  CF70E Information Reform

CF70E Information Reform

分类: IT文章 • 2023-11-12 19:35:48

题意：给你一棵树，要选择若干节点，若一个点i没有选择，则有(d(dis(i,j)))的代价，其中j被选择。选择一个点代价为k，求最小代价。
首先，考虑这样一个问题：
如果距离a的最近被选点为i，距离b的最近被选点也是i，那么a到b的路径上的点的最近被选点都是i。
考虑一条链：设Ax是链上第x个点，那么点y到Ax的距离fy(x)随x的增加，先下降，再上升。（这个显然）。
那么假设a到b路径上的c，最近点不是i而是j。
那么，(dis(a,i)<dis(a,j)，dis(c,i)>dis(c,j)，dis(b,i)<dis(b,j))。
就是说(fi)和(fj)有两个交点。但这是不可能的。
所以，如果距离a的最近被选点为i，距离b的最近被选点也是i，那么a到b的路径上的点的最近被选点都是i一定成立。
换句话说，以i为最近点的j是一个连通块。
这样，我们设(dp(i,j))表示i的最近点是j的状态。再维护(f(i))表示(dp(i,j))的最小值。
那么，对于i的每个儿子v，枚举它的最近点a，则转移到(dp(v,a))。
但如果(j=a)，那么对于v来说，a已经选择过了，则转移到(dp(v,a)-k)。
维护(f(i))后就是(dp(i,j)=min(f(v),dp(v,j)-k)+d(dis(i,j))+k)。
因为要输出方案，再记录一下转移的位置。
(dis)数组可以(O(n^2))预处理出。
代码：

#include <stdio.h> 
int fr[182],ne[362],v[362],bs = 0;
void addb(int a, int b) {
	v[bs] = b;
	ne[bs] = fr[a];
	fr[a] = bs++;
}
int dp[182][182],wz[182],sz[182],cd[182][182],n,k;
int fa[182],sd[182],ans[182],zy[362][182];
void dfs0(int u, int f) {
	fa[u] = f;
	sd[u] = sd[f] + 1;
	for (int i = fr[u]; i != -1; i = ne[i]) {
		if (v[i] != f) dfs0(v[i], u);
	}
}
int dfscd(int a, int b) {
	if (a == b) return 0;
	if (cd[a][b]) return cd[a][b];
	if (sd[a] > sd[b]) cd[a][b] = dfscd(fa[a], b) + 1;
	else cd[a][b] = dfscd(a, fa[b]) + 1;
	return cd[a][b];
}
void dfs(int u, int f) {
	for (int i = fr[u]; i != -1; i = ne[i]) {
		if (v[i] != f) dfs(v[i], u);
	}
	for (int a = 1; a <= n; a++) {
		dp[u][a] = sz[cd[u][a]] + k;
		for (int i = fr[u]; i != -1; i = ne[i]) {
			if (v[i] == f) continue;
			int t = dp[v[i]][wz[v[i]]];
			if (dp[v[i]][a] - k < t) {
				t = dp[v[i]][a] - k;
				zy[i][a] = a;
			} else zy[i][a] = wz[v[i]];
			dp[u][a] += t;
		}
		if (a == 1 || dp[u][a] < dp[u][wz[u]]) wz[u] = a;
	}
}
void dfs1(int u, int f, int a) {
	ans[u] = a;
	for (int i = fr[u]; i != -1; i = ne[i]) {
		if (v[i] != f) dfs1(v[i], u, zy[i][a]);
	}
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) fr[i] = -1;
	for (int i = 1; i < n; i++) scanf("%d", &sz[i]);
	for (int i = 0; i < n - 1; i++) {
		int a,b;
		scanf("%d%d", &a, &b);
		addb(a, b);
		addb(b, a);
	}
	dfs0(1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j && cd[i][j] == 0) dfscd(i, j);
		}
	}
	dfs(1, 0);
	int z = 1;
	for (int i = 2; i <= n; i++) {
		if (dp[1][i] < dp[1][z]) z = i;
	}
	printf("%d
", dp[1][z]);
	dfs1(1, 0, z);
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

如果信息要求更精确（因为上述做法这个最近点不一定联通，即可能重复，被考虑多次）。
在子节点v的最近点与当前点u相同时，直接转移，不需要考虑贡献。
否则，必须满足u的最近点不在v子树内，并且v的最近点在它的子树内。
这样，就可以避免重复的问题了。
每个最远点的贡献可以在(f(u,u))时考虑，也可以在每个连通块的顶部考虑。
例题：bzoj Rbtree。

相关推荐