5367 : B68 - ALGO 급행
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 역 중 일부를 특급역으로 지정하려고 합니다. 역 $i$를 특급역으로 지정하면 $P_i$원의 이익을 얻습니다. 또한 "역 $A_j$를 특급역으로 지정한다면 역 $B_j$도 특급역으로 지정해야 한다"는 $M$개의 제안이 있습니다. 모든 제안을 지키면서 얻을 수 있는 최대 이익은 얼마입니까?
[제약 조건]
• $2 \le N \le 150$
• $1 \le M \le 150$
• $|P_i| \le 150$
• $1 \le A_j , B_j \le N$
• $A_j \neq B_j$
• $j \neq k$ 이면 $(A_j,B_j) \neq (A_k,B_k)$ 입니다.
• 입력되는 모든 값은 정수입니다.
[제약 조건]
• $2 \le N \le 150$
• $1 \le M \le 150$
• $|P_i| \le 150$
• $1 \le A_j , B_j \le N$
• $A_j \neq B_j$
• $j \neq k$ 이면 $(A_j,B_j) \neq (A_k,B_k)$ 입니다.
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 역의 수 $N$ 과 제안의 수 $M$ 이 주어집니다.
둘째 줄에 각 역의 이익 $P_1, P_2, \dots, P_N$ 이 주어집니다.
다음 $M$ 개 줄에 제안 $A_j, B_j$ 가 주어집니다.
둘째 줄에 각 역의 이익 $P_1, P_2, \dots, P_N$ 이 주어집니다.
다음 $M$ 개 줄에 제안 $A_j, B_j$ 가 주어집니다.
출력 설명
최대 이익을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2
3 4 -1 -5 5
1 3
2 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7도움
역 1, 역 3, 역 5를 특급역으로 지정하면 이익이 7원이 되며, 이것이 최대입니다.