A90525.「USACO 2025.1 Platinum」DFS Order

题目来自 USACO 2025 January Contest, Platinum Problem 1. DFS Order

Bessie 有一个无向简单图，结点编号为 $1\dots N$（$2\le N\le 750$）。她通过调用函数 $\texttt{dfs}(1)$ 生成该图的一个深度优先搜索（depth-first search，DFS）序，函数由以下 C++ 代码定义。各邻接表（对于所有 $1\le i\le N$ 的 $\texttt{adj}[i]$）在开始深度优先搜索之前可以任意排列，因此一个图可以有多个可能的 DFS 序。

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // 邻接表
vector<int> dfs_order;

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = true;
    dfs_order.push_back(x);
    for (int y : adj[x]) dfs(y);
}

给定图的初始状态以及修改每条边状态的代价。具体地说，对于每对满足 $1\le i<j\le N$ 的结点 $(i,j)$，给定一个整数 $a_{i,j}$（$0<|a_{i,j}|\le 1000$），其中

• 如果 $a_{i,j}>0$，则边 $(i,j)$ 当前不在图中，可以以代价 $a_{i,j}$ 添加。
• 如果 $a_{i,j}<0$，则边 $(i,j)$ 当前在图中，可以以代价 $-a_{i,j}$ 移除。

求使得 $[1,2\dots,N]$ 成为一个可能的 DFS 序的最小总代价。

输入的第一行包含 $N$。

以下 $N-1$ 行，第 $j-1$ 行包含 $a_{1,j}, a_{2,j}, \dots, a_{j-1,j}$，以空格分隔。

输出使得 $[1,2,\dots, N]$ 成为一个可能的 DFS 序的最小总代价。