2025勰码公益营 B 班 37号 作业 1-1（一共两道题）
porse
·
·
个人记录
P3177 [HAOI2015] 树上染色 题解
题目大意
将 n 个点的树染 K 个黑点，其余为白点，使黑点两两距离和加白点两两距离和最大。
## 思路
这个“两两距离和”不太好搞，于是我们考虑拆贡献，每个边的贡献就是两侧黑点数乘积加白点数乘积，这个是好维护的。
对于树上染色问题，我们通常考虑 dp，这题也一样。令 $dp_{u, j}$ 为 $u$ 的子树中染了 $j$ 个黑点的答案。
转移就是一个 $sz_u$ 中取 $K$ 的问题，可以直接 树上背包 解决。
转移方程：
$$
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. 把 $k$ 个点染黑和把 $n - k$ 个点染黑是等价的，所以代码开头可以写一句`k = min(k, n - k)`。
2. $dp_{u, j}$ 中 $j$ 的最大值到 $\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 方格取数加强版](https://www.luogu.com.cn/problem/P2045) 题解
## 题目大意
给定一个 $n\times n$ 的矩阵 $a$，每次从 $(1,1)$ 走到 $(n,n)$，只能往右下走，取路径上的数字，走 $k$ 次，每个数字最多取一次，问取到数字和的最大值。
## 分析
如果走一次，那么这道题可以 dp 做，但是走 $k$ 次加上每个数字最多取一次这个条件，我们就只能另寻他法。
我们观察数据范围：$n \le 50$，网络流在脑海中浮现。
因为这道题要求的是和，而最大流本质是 $\min\{flow\}$，而费用是相加，所以我们可以把 $a_{i,\,j}$ 换成费用，这样就解决了求和的问题，但我们要求的是最大和，所以我们可以使用**最大费用最大流**。
由于费用在原矩阵的点上，所以我们可以考虑**拆点**来做：
- 把原矩阵中的点拆成入点与出点，将每对入点、出点连两条边，一条流量为 $1$，费用为 $a_{i,\,j}$，第二条流量为 $k - 1$，费用为 $0$，这样我们就完美地解决了每个数只能取一次的问题。
- $a_{i-1,\,j}$ 与 $a_{i,\,j - 1}$ 的出边连线，流量为 $k$ 费用为 $0$。
建完边就可以跑最大费用最大流了，它和最小费用最大流唯一的区别就是 spfa 找最长路，具体细节见代码
**注意，我们拆点了，所以 $maxn = 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;
}
```