Задача . DFS Order

У Беси есть простой неориентированный граф с вершинами, помеченными \(1\dots N\) (\(2\le N\le 750\)). Она генерирует поиск в глубину графа вызывая функцию \(\texttt{dfs}(1)\), описанную следующим C++ кодом. Каждый список соседних вершин (\(\texttt{adj}[i]\) для всех \(1\le i\le N\)) может быть переставлен произвольно перед началом поиска в глубину, поэтому граф может иметь множество возможных DFS-порядков.

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);
}

Вам дано начальное состояние графа, а также стоимость изменения состояния каждого ребра. А именно, для каждой пары вершин \((i,j)\) удовлетворяющей \(1\le i<j\le N\), Вам дано целое число \(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-обходом.

10