R03469
Maximum Weight Without Conflicts
골드 IV레이팅
의견: 0
설명
\(N\)개의 물건이 있고 물건 \(i\)의 가중치는 \(w_i\)이다. 일부 물건 쌍은 서로 충돌하여 동시에 선택할 수 없다. 충돌하는 쌍이 없도록 물건의 부분집합을 골라 가중치 합을 최대화하고, 그 최대 합을 출력하시오 (아무것도 고르지 않으면 가중치는 \(0\)이다).
제약
입력 형식
첫 줄에 \(N\) (\(1 \le N \le 20\))이 주어진다. 둘째 줄에 \(N\)개의 정수 \(w_0 \dots w_{N-1}\)이 주어진다 (\(1 \le w_i \le 1000\)). 셋째 줄에 충돌 쌍의 개수 \(E\)가 주어지고, 이어지는 \(E\)개의 줄에는 서로 다른 두 인덱스 \(u\ v\)가 주어진다 (\(0 \le u, v < N\)).
출력 형식
얻을 수 있는 최대 가중치 합을 출력한다.
예제 1
입력
4
3 4 5 6
2
0 1
2 3
출력
10
예제 2
입력
3
5 5 5
3
0 1
1 2
0 2
출력
5
예제 3
입력
3
1 2 3
0
출력
6
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그
평가 및 의견
Maximum Weight Without Conflicts
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Maximum Weight Without Conflicts
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기