RiseOJ – DFS 순서

설명

베시는 정점에 $1\dots N$ ( $2\le N\le 750$ )의 번호가 붙은 단순 무방향 그래프를 가지고 있다. 그녀는 아래 C++ 코드로 정의된 함수 $\texttt{dfs}(1)$ 을 호출하여 그래프의 깊이 우선 탐색(DFS) 순서를 생성한다. 깊이 우선 탐색을 시작하기 전에 각 인접 리스트(모든 $1\le i\le N$ 에 대한 $\texttt{adj}[i]$ )를 임의로 재배열할 수 있으므로, 하나의 그래프는 여러 가지 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);
}

그래프의 초기 상태와 각 간선의 상태를 바꾸는 비용이 주어진다. 구체적으로, $$1\le i을 만족하는 모든 정점 쌍 \((i,j)$에 대해 정수 $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 순서가 되도록 그래프를 바꾸는 데 드는 총비용의 최솟값을 구하시오.

Problem credits: Benjamin Qi

제약

배점

입력 4-9: 모든 $a_{i,j}>0$
입력 10-16: $N\le 50$
입력 17-23: 추가 제약이 없다.

Problem credits: Benjamin Qi

입력 형식

첫째 줄에 $$N$$ 이 주어진다.

다음 $$N-1$$ 개의 줄이 이어진다. $$j-1$$ 번째 줄에 $a_{1,j}, a_{2,j}, \dots, a_{j-1,j}$ 가 공백으로 구분되어 주어진다.

출력 형식

$[1,2,\dots, N]$ 이 가능한 DFS 순서가 되도록 그래프를 바꾸는 최소 비용을 출력한다.

예제 1

입력

출력

설명

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]$$ .

예제 2

입력

5
-1
10 -2
10 -7 10
-6 -4 -5 10

출력

설명

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$$ .

예제 3

입력

출력

설명

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$$ .

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > January > Platinum

올림피아드 > USACO > 2024-2025 > January > Platinum

태그

JudgeUSACO

DFS 순서

평가 및 의견

풀이 제출