P11676 [USACO25JAN] DFS Order P
rlc202204
·
·
题解
P11676 [USACO25JAN] DFS Order P
题意：
有一个 n 个点的无向图和一个 n \times n 的矩阵 a，a_{i,j} > 0 说明这条边当前不在，加入的代价是 a_{i,j}，a_{i,j} < 0 说明这条边当前在，删除的代价是 -a_{i,j}。
可以增删一些边，使得存在一个 dfs 序是 1,2,3,\dots,n。
**思路：**
这个数据范围不是网络流就是 dp，经过尝试会发现网络流不太好做，考虑 dp。
如果我们当前搜到了 $i$，则我们要求除了走过来的这条边，$i$ 不能和前面的点有任何连边。
我们考虑区间 dp：设 $f(i,j)$ 表示进入 $i$ 的子树中，最后一个搜完的是 $j$。
首先，有 $\sum_{k=j+1}^n \max\{0,-a_{i,k}\}$ 的代价，因为如果 $j$ 之后 $i$ 回溯了那么是不能和后面有边的。
我们先不考虑这个代价，我们类似树形 $dp$ 考虑一个子树一个子树的加入。
枚举一个 $j$，考虑能转移到哪些状态。
我们枚举下一个子树到 $k$，则转移就是：
$$
f(i,j) + f(j+1,j+k) + \max\{0,a_{i,j+1}\} \to f(i,j+k)
$$
这样就能 $O(n^2)$ 求出所有 $f_i(j)$，总的时间复杂度就是 $O(n^3)$。
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 755;
const int inf = 0x3f3f3f3f;
int n;
int a[N][N] = {{0}};
int f[N][N] = {{0}}, g[N][N] = {{0}};
void cmn(int &x, int y) {
x = min(x, y);
}
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
scanf("%d", &a[j][i]);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++)
g[i][j] = max(0, -a[i][j]);
for (int j = n - 1; j >= i + 1; j--)
g[i][j] += g[i][j + 1];
}
memset(f, 0x3f, sizeof f);
for (int i = n; i >= 1; i--) {
f[i][i] = 0;
for (int j = i; j <= n; j++) {
if (f[i][j] != inf) {
for (int k = 1; j + k <= n; k++) {
cmn(f[i][j + k], f[i][j] + f[j + 1][j + k] + max(0, a[i][j + 1]));
}
}
}
for (int j = i; j <= n; j++)
f[i][j] += g[i][j + 1];
}
cout << f[1][n] << endl;
return 0;
}
```