DFS Order

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 $\text{dfs}(1)$, defined by the following C++ code. Each adjacency list ($\text{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<j\le N$, 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.

Initially, the graph contains no edges. $(1,2),(2,3),(2,4)$ can be added for a total cost of $1+3+6$. The graph now has two possible DFS orderings: $[1,2,3,4],[1,2,4,3]$.

Initially, the graph contains edges $(1,2),(2,3),(2,4),(1,5),(2,5),(3,5)$. Edge $(3,5)$ can be removed for a cost of $5$.

Initially, the graph contains edges $(1,2),(1,3),(2,4)$. Edge $(2,4)$ can be removed and edge $(1,4)$ can be added for a total cost of $5+4=9$.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Submit