专栏文章

2025勰码公益营 B 班 37号 作业 1-1（一共两道题）

pporse
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqcihgd
此快照首次捕获于
2025/12/04 02:33
3 个月前
此快照最后确认于
2025/12/04 02:33
3 个月前
查看原文

P3177 [HAOI2015] 树上染色 题解

题目大意

将 nn 个点的树染 KK 个黑点，其余为白点，使黑点两两距离和加白点两两距离和最大。
1≤K≤n≤20001 \le K \le n \le 2000。

思路

这个“两两距离和”不太好搞，于是我们考虑拆贡献，每个边的贡献就是两侧黑点数乘积加白点数乘积，这个是好维护的。
对于树上染色问题，我们通常考虑 dp，这题也一样。令 dpu,jdp_{u, j} 为 uu 的子树中染了 jj 个黑点的答案。
转移就是一个 szusz_u 中取 KK 的问题，可以直接 树上背包 解决。
转移方程：
dpu,j=max(dpu,j,dpu,j−k+dpson,k+k∗(K−k)∗now.v+(sz[now.to]−k)∗(n−K−sz[now.to]+k)∗val);dp_{u, j} = max(dp_{u, j}, dp_{u, j - k} + dp_{son,k} + k * (K - k) * now.v + (sz[now.to] - k) * (n - K - sz[now.to] + k) * val);

一些小优化

  1. 把 kk 个点染黑和把 n−kn - k 个点染黑是等价的，所以代码开头可以写一句k = min(k, n - k)。
  2. dpu,jdp_{u, j} 中 jj 的最大值到 min⁡(szu,k)\min(sz_u, k) 就行了。

Code

CPP
#include <bits/stdc++.h>
using namespace std;

#define int long long
constexpr int maxn = 2010;

int n, K, sz[maxn], dp[maxn][maxn];
struct edge {
	int to, v;
} ;
vector <edge> G[maxn];

void dfs(int u, int fa) { // 树形 dp
	sz[u] = 1;
	for (edge now : G[u]) {
		if (now.to == fa) continue;
		dfs(now.to, u);
		sz[u] += sz[now.to];
		for (int j = max(K, sz[u]); j >= 0; j--) { // 小优化2
			for (int k = max(j - sz[u] + sz[now.to], 0ll); k <= min(j, sz[now.to]); k++) {
				dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[now.to][k] + k * (K - k) * now.v + (sz[now.to] - k) * (n - K - sz[now.to] + k) * now.v);
			}
		}
	}
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	cin >> n >> K;
	K = min(K, n - K); // 小优化 1
	for (int i = 1, a, b, c; i < n; i++) {
		cin >> a >> b >> c;
		G[a].push_back({b, c});
		G[b].push_back({a, c});
	}

	dfs(1, 0);

	cout << dp[1][K] << endl;

	return 0;
}

P2045 方格取数加强版 题解

题目大意

给定一个 n×nn\times n 的矩阵 aa，每次从 (1,1)(1,1) 走到 (n,n)(n,n)，只能往右下走，取路径上的数字，走 kk 次，每个数字最多取一次，问取到数字和的最大值。

分析

如果走一次，那么这道题可以 dp 做，但是走 kk 次加上每个数字最多取一次这个条件，我们就只能另寻他法。
我们观察数据范围：n≤50n \le 50，网络流在脑海中浮现。
因为这道题要求的是和，而最大流本质是 min⁡{flow}\min\{flow\}，而费用是相加，所以我们可以把 ai, ja_{i,\,j} 换成费用，这样就解决了求和的问题，但我们要求的是最大和，所以我们可以使用最大费用最大流。
由于费用在原矩阵的点上，所以我们可以考虑拆点来做：
  • 把原矩阵中的点拆成入点与出点，将每对入点、出点连两条边，一条流量为 11，费用为 ai, ja_{i,\,j}，第二条流量为 k−1k - 1，费用为 00，这样我们就完美地解决了每个数只能取一次的问题。
  • ai−1, ja_{i-1,\,j} 与 ai, j−1a_{i,\,j - 1} 的出边连线，流量为 kk 费用为 00。
建完边就可以跑最大费用最大流了，它和最小费用最大流唯一的区别就是 spfa 找最长路，具体细节见代码
注意，我们拆点了，所以 maxn=50×50×2=5000maxn = 50 \times 50 \times 2 = 5000。

Code

CPP
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 5010;

struct edge {
	int to, v, costt, rev; //rev的目的是寻找反向边，定义标准是 G[to][rev] = from
} now;
int n, k, u, a, s, t, maxcost;
int dist[maxn], book[maxn], pree[maxn], pin[maxn], minn[maxn]; // pree: 路径的上一个节点，pin: 上一个节点到当前点的路径的下标
vector <edge> G[maxn];
queue <int> q;

int point1(int x, int y) { //入点
	return (x - 1) * n + y;
}
int point2(int x, int y) { //出点
	return (((x - 1) * n + y) + n * n);
}

void add(int from, int to, int v, int costt) { //连边
	G[from].push_back({to, v, costt, G[to].size()});
	G[to].push_back({from, 0, -costt, G[from].size() - 1});
}

void input() { //输入&建图
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a;
			add(point1(i, j), point2(i, j), 1, a);
			add(point1(i, j), point2(i, j), k - 1, 0);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i > 1) add(point2(i - 1, j), point1(i, j), k, 0);
			if (j > 1) add(point2(i, j - 1), point1(i, j), k, 0);
		}
	}
	s = point1(1, 1);
	t = point2(n, n);
	return ;
}

bool spfa() { //spfa不多介绍了，只说一下最长路的不同点
	for (int i = s; i <= t; i++) {
		book[i] = 0;
		dist[i] = -2147483648;//不同1：dist初始化为 -INF
	}
	q.push(s);
	book[s] = 1;
	dist[s] = 0;
	minn[s] = 2147483647;
	while (!q.empty()) {
		u = q.front();
		q.pop();
		book[u] = 0;
		for (int i = 0; i < G[u].size(); i++) {
			now = G[u][i];
			if (!now.v) continue;
			if (dist[now.to] >= dist[u] + now.costt) continue; //不同2：松弛判断
			dist[now.to] = dist[u] + now.costt;
			pree[now.to] = u;
			pin[now.to] = i;
			minn[now.to] = min(now.v, minn[u]);
			if (!book[now.to]) q.push(now.to), book[now.to] = 1;
		}
	}
	return dist[t] != -2147483648;//不同3：判断
}
void update() { //修改
	u = t;
	maxcost += dist[t] * minn[t];
	while (u != s) {
		G[pree[u]][pin[u]].v -= minn[t];
		G[u][G[pree[u]][pin[u]].rev].v += minn[t]; // 寻找反向边（但是亲测邻接表比链式前向星快）
		u = pree[u];
	}
	return ;
}

void solve() {
	while (spfa()) update();
	cout << maxcost << '\n';
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	input();
	solve();

	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...