도시 순회 보상
플래티넘 I의견: 0
\(N\)개의 도시가 있고, 도시 사이에 \(M\)개의 단방향 도로가 있다. 도시 \(i\)를 처음 방문하면 보상 \(v_i\)를 얻는데, 이 값은 음수일 수도 있다.
한 도시에서 출발하여 도로를 따라 이동한다. 같은 도시를 여러 번 지날 수 있으나 보상은 처음 방문할 때 한 번만 얻는다. 어떤 도시에서 출발해 어디서 멈추든 자유이며, 얻을 수 있는 보상의 합의 최댓값을 구하여라.
\(1 \le N \le 100{,}000\)
\(0 \le M \le 300{,}000\)
\(-10^9 \le v_i \le 10^9\)
\(1 \le a, b \le N\). 자기 자신으로의 도로나 중복 도로가 있을 수 있다.
첫 줄에 도시의 수 \(N\)과 도로의 수 \(M\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(v_1, \dots, v_N\)이 주어진다.
다음 \(M\)개의 줄에 각각 두 정수 \(a\), \(b\)가 주어지며, 도시 \(a\)에서 \(b\)로 가는 단방향 도로를 의미한다.
얻을 수 있는 보상의 합의 최댓값을 한 줄에 출력한다.
4 4
3 4 5 -2
1 2
2 3
3 1
3 4
12도시 1,2,3은 서로 오갈 수 있어 하나의 SCC를 이루며 보상 합은 3+4+5=12이다. 여기서 도시4(-2)로 더 가면 10이 되어 줄어든다. 따라서 SCC{1,2,3}만 모두 방문해 12를 얻는 것이 최대이다.
3 2
-5 -1 -3
1 2
2 3
-1모든 보상이 음수이다. 어디서 출발하든 한 도시만 방문하고 멈추는 것이 유리하며, 가장 덜 손해인 도시2(-1)에서 출발해 바로 멈추면 -1이 최댓값이다.
riseoj 작성
출처 Original
평가 및 의견
도시 순회 보상
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
도시 순회 보상