연구 과제 선정
플래티넘 I의견: 0
연구소에는 \(N\)개의 과제가 있다. \(i\)번 과제를 수행하면 순이익 \(p_i\)를 얻는데, 이 값은 음수일 수도 있다(비용이 더 큰 경우).
어떤 과제에는 선행 과제가 있다. 즉 \(i\)번 과제를 수행하려면 반드시 지정된 선행 과제들도 함께 수행해야 한다. 선행 관계는 여러 단계로 이어질 수 있다.
수행할 과제의 부분집합을 자유롭게 고를 수 있다(아무것도 고르지 않아도 된다). 단, 고른 집합은 모든 선행 관계를 만족해야 한다. 이때 얻을 수 있는 순이익의 합의 최댓값을 구하여라.
\(1 \le N \le 5{,}000\)
\(0 \le M \le 20{,}000\)
\(-10^6 \le p_i \le 10^6\)
\(1 \le a, b \le N\), \(a \ne b\)
첫 줄에 과제의 수 \(N\)과 선행 관계의 수 \(M\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(p_1, p_2, \dots, p_N\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 각각 두 정수 \(a\), \(b\)가 주어지며, 이는 \(a\)번 과제를 수행하려면 \(b\)번 과제도 수행해야 함을 의미한다.
얻을 수 있는 순이익의 합의 최댓값을 한 줄에 출력한다.
4 2
10 -4 6 -3
1 2
3 4
9과제1(이익10)은 과제2(-4)를 요구해 둘을 함께 하면 6. 과제3(6)은 과제4(-3)를 요구해 함께 하면 3. 둘 다 수행하면 6+3=9. 과제1,2만 하면 6, 과제3,4만 하면 3이므로 최댓값은 9이다.
3 2
-5 -2 -7
1 2
2 3
0모든 과제의 이익이 음수이므로 아무 과제도 수행하지 않는 것이 최선이다. 답은 0.
riseoj 작성
출처 Original
평가 및 의견
연구 과제 선정
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
연구 과제 선정