페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8264
서브태스크

DFS Order 1초 1024MB

문제

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 순서를 만들 수 있도록 최소 비용을 구하는 것입니다.


입력

첫 번째 줄에는 정점의 수 N이 주어집니다.

그 다음 N-1개의 줄에는 각 줄마다 1부터 N까지의 정점에 대한 간선 상태가 주어집니다. 각 값 a_{i,j}는 두 정점 i와 j 사이의 간선 상태를 나타냅니다.


출력

첫 줄에 그래프를 변경하는 최소 비용을 출력한다.


부분문제

번호 점수 조건
#120점

a_{i,j} > 0

#230점

N≤50

#350점

추가 제약 조건 없음


예제1

입력
4
1
23
40611
출력
10

처음에는 그래프에 간선이 없습니다. (1,2), (2,3), (2,4)를 추가할 수 있으며, 총 비용은 1+3+6입니다. 이제 그래프는 두 가지 가능한 DFS 순서인 [1,2,3,4]와 [1,2,4,3]을 가질 수 있습니다.


예제2

입력
5
-1
10-2
10-710
-6-4-510
출력
5

처음에는 그래프에 간선 (1,2), (2,3), (2,4), (1,5), (2,5), (3,5)가 있습니다. 간선 (3,5)는 비용 5로 제거할 수 있습니다.


예제3

입력
4
-1
-2300
4-56
출력
9

처음에는 그래프에 간선 (1,2), (1,3), (2,4)가 있습니다. 간선 (2,4)는 제거할 수 있고, 간선 (1,4)는 추가할 수 있습니다. 총 비용은 5 + 4 = 9입니다.


출처

USACO 2025 January Platinum

역링크