Bessie는 정점이 1부터 N까지 라벨이 붙은 간단한 무방향 그래프를 가지고 있습니다. 그녀는 그래프의 깊이 우선 탐색(DFS) 순서를 생성하려고 합니다. DFS 순서는 다음과 같은 C++ 코드로 정의된 dfs(1)을 호출하여 생성됩니다.

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

각 정점에 대해 인접 리스트(adj[i] for all 1≤i≤N)가 주어지며, 이 리스트는 DFS를 시작하기 전에 임의로 순서를 변경할 수 있습니다. 그래서 같은 그래프라도 여러 개의 가능한 DFS 순서를 가질 수 있습니다.

그래프의 초기 상태와 각 간선의 상태를 변경하는 비용이 주어집니다. 즉, 각 두 정점 (i, j)에 대해 다음과 같은 조건이 주어집니다.

만약 ai,j > 0이라면, 간선 (i,j)는 현재 그래프에 없고, 추가하는 데 ai,j 만큼의 비용이 듭니다.
만약 ai,j < 0이라면, 간선 (i,j)는 현재 그래프에 있으며, 제거하는 데 −ai,j 만큼의 비용이 듭니다.

이 문제의 목표는 그래프의 상태를 변경하여 [1, 2, ..., N] 순서가 가능한 DFS 순서를 만들 수 있도록 최소 비용을 구하는 것입니다.

#8264 upload 1 done - how_to_reg - call_split Subtarea

DFS Order timer 1s memory 1024MB

#8264
Subtarea

DFS Order 1s 1024MB