Bessie has a simple undirected graph with vertices labeled \(1\dots N\)
(\(2\le N\le 750\)). She generates a depth-first search (DFS) order of the graph
by calling the function \(\texttt{dfs}(1)\), defined by the following C++ code.
Each adjacency list (\(\texttt{adj}[i]\) for all \(1\le i\le N\)) may be permuted arbitrarily before starting
the depth first search, so a graph can have multiple possible DFS orders.

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // adjacency list
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);
}

You are given the initial state of the graph as well as the cost to change the
state of each edge. Specifically, for every pair of vertices \((i,j)\) satisfying
\(1\le i, you are given an integer \(a_{i,j}\) (\(0<|a_{i,j}|\le 1000\)) such
that

• If \(a_{i,j}>0\), edge \((i,j)\) is not currently in the graph, and can be added for cost \(a_{i,j}\).
• If \(a_{i,j}<0\), edge \((i,j)\) is currently in the graph, and can be removed for cost \(-a_{i,j}\).

Determine the minimum total cost to change the graph so that \([1,2\dots,N]\) is a
possible DFS ordering.

Problem credits: Benjamin Qi

SCORING

• Inputs 4-9: All \(a_{i,j}>0\)
• Inputs 10-16: \(N\le 50\)
• Inputs 17-23: No additional constraints.

Problem credits: Benjamin Qi

The first line contains \(N\).

Then \(N-1\) lines follow. The \(j-1\)th line contains
\(a_{1,j}, a_{2,j}, \dots, a_{j-1,j}\) separated by spaces.

The minimum cost to change the graph so that \([1,2,\dots, N]\) is a possible DFS
ordering.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > January > Platinum