33498번 - 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 dfs(1ドル$), defined by the following C++ code. Each adjacency list (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.

입력

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.

제한

힌트