24434번 - 전력공급 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 13 | 7 | 6 | 85.714% |
문제
Bob이 살고 있는 Alberta 도시에는 $n$개의 건물이 있고 $1$번부터 $n$번까지 번호가 붙어있다. 각 건물은 일정량의 전기를 생산하고 소비한다. $v_i$는 $i$번째 빌딩의 전력 생산량에서 소비량을 뺀 값으로 해당 빌딩의 "잉여 전력"을 나타낸다. 만약 건물의 소비량이 생산량보다 크다면 $v_i$값은 음수가 된다. $v_i$가 0인 경우는 없고, 항상 정수이다.
일부 건물은 서로 전선으로 연결되어 있어서 한 건물에서 생산한 전력의 일부를 다른 건물에 보내주기도 한다. 현재 전선은 총 $m$개가 있고 $1$번부터 $m$번까지 번호가 붙어있다. $j$번째 전선은 건물 $x_j$에서 건물 $y_j$로 $z_j > 0$만큼의 전력을 공급해 준다. 각 전선은 방향성이 있고, 두 건물 사이에는 같은 방향의 전선은 최대 한 개만 있을 수 있다.
전기가 매우 중요한 자원이 되었기 때문에 Bob은 $n$개의 건물 중 일부 건물을 사들여 이 건물들의 잉여 전력 총량이 최대가 되도록 하고 싶다. 구체적으로, $S$가 $\{1, 2, \dots, n\}$의 부분집합일 때, 즉, Bob이 $S$에 속한 건물들을 사기로 했을 때, $S$의 잉여 전력 총량인 $V(S)$는 아래와 같이 정의 된다.
- ($S$에 속한 건물들의 잉여 전력 총합) - ($S$에 속한 건물들이 $S$에 속하지 않은 건물들에 전선을 통해 공급하는 전력의 총합)
예를 들어 $n = 3$, $m = 2$, $v_1 = 4$, $v_2 = -1$, $v_3 = -2$, $x_1 = 1$, $x_2 = 2$, $y_1 = 2$, $y_2 = 3$, $z_1 = 1$, $z_2 = 1$ 이라 하자.
- 건물 $1$은 자체 전력 생산량이 소비량보다 커서 잉여 전력이 $4$이며 다른 두 건물은 잉여 전력이 음수이다.
- $1$번 전선은 건물 $1$에서 건물 $2$로 $1$만큼의 전력을 공급한다.
- $2$번 전선은 건물 $2$에서 건물 $3$으로 $1$만큼의 전력을 공급한다.
이 예제에서 Bob이 건물을 살 방법은 총 $2^3 = 8$가지가 있는데, 각 경우에 대한 잉여 전력 총량은 아래와 같다.
- $S$가 공집한인 경우: $V(S) = 0$.
- $S = \{1\}$인 경우: $V(S) = 4 - 1 = 3$.
- $S = \{2\}$인 경우: $V(S) = (-1) - 1 = -2$.
- $S = \{3\}$인 경우: $V(S) = (-2) - 0 = -2$.
- $S = \{1, 2\}$인 경우: $V(S) = (4-1) - 1 = 2$. 이 경우, $1$번 전선의 경우 건물 $1$에서 건물 $2$로 전력을 공급하지만 두 건물 모두 사들인다면 위 정의에 따라 $V(S)$를 계산할 때 고려하지 않는다.
- $S = \{2, 3\}$인 경우: $V(S) = (-1-2) - 0 = -3$.
- $S = \{1, 3\}$인 경우: $V(S) = (4-2) - 1 = 1$.
- $S = \{1, 2, 3\}$인 경우: $V(S) = (4-1-2) - 0 = 1$.
$8$가지 방법 중 잉여 전력 총량이 최대가 되는 경우는 $S = \{1\}$인 경우이다.
다른 예로, $n = 2$, $m = 1$, $v_1 = 1$, $v_2 = -5$, $x_1 = 1$, $y_1 = 2$, $z_1 = 1$이라 하자.
- $S$가 공집합인 경우: $V(S) = 0$.
- $S = \{1\}$인 경우: $V(S) = 1 - 1 = 0$.
- $S = \{2\}$인 경우: $V(S) = -5$.
- $S = \{1, 2\}$인 경우: $V(S) = (1-5) - 0 = -4$.
총 $4$가지 방법 중 잉여 전력 총량이 최대가 되는 경우는 $S = \{1\}$ 또는 $S$가 공집합인 경우이다.
입력으로 $n$, $m$, $v$, $x$, $y$, $z$가 주어졌을 때, Bob이 달성할 수 있는 최대 잉여 전력 총량을 구해보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $n$과 $m$이 공백으로 구분되어 주어진다.
둘째 줄에는 각 건물의 잉여 전력량 $v_i$이 공백으로 구분되어 주어진다.
다음 $m$줄에 걸쳐 각 줄에 세 개의 정수 $x_j$, $y_j$, $z_j$주어진다. 이는 건물 $x_j$에서 건물 $y_j$로 $z_j$만큼의 전력이 공급되고 있음을 나타낸다.
출력
각 테스트 케이스의 정답인 Bob이 달성할 수 있는 최대 잉여 전력량을 각 줄에 출력한다.
제한
- $1 ≤ i ≤ n$인 모든 $i$에 대하여 $-100\,000 ≤ v_i ≤ 100\,000$ 이고 $v_i \ne 0$.
- $1 ≤ j ≤ m$인 모든 $j$에 대하여 $x_j \ne y_j$이고 $1 ≤ x_j, y_j ≤ n$, 그리고 $1 ≤ z_j ≤ 100\,000$.
- $1 ≤ j < k ≤ m$인 모든 $j$, $k$에 대하여 $x_j = x_k$이고 동시에 $y_j = y_k$인 경우는 없다. 즉, 모든 전선은 방향을 고려했을 때 고유하다.
서브태스크 1 (5점)
- $1 ≤ T ≤ 20$
- $2 ≤ n ≤ 15$
- $1 ≤ m ≤ \min(100, n(n-1))$
서브태스크 2 (25점)
- $1 ≤ T ≤ 20$
- $2 ≤ n ≤ 200$
- $1 ≤ m ≤ \min(8000, n(n-1))$
예제 입력 1
6 2 1 1 -2 1 2 3 2 1 1 -2 2 1 3 3 2 4 -1 -2 1 2 1 2 3 1 3 6 10 10 10 1 2 2 2 1 3 1 3 4 3 1 5 2 3 6 3 2 7 2 1 1 -5 1 2 1 3 2 1 1 -2 1 3 1 2 3 1
예제 출력 1
0 1 3 30 0 0
- 예제 1: 아무 건물도 사지 않는 것이 최선이다.
- 예제 2: $S = \{1}$이 최선이다.
- 예제 3: 본문에서 다루었다.
- 예제 4: 모든 건물을 다 사는 것이 최선이다.
- 예제 5: 본문에서 다루었다.
- 예제 6: 여러 가지 방법이 존재한다.
시간 제한
- Java 8: 2 초
- Python 3: 2 초
- PyPy3: 2 초
- Java 8 (OpenJDK): 2 초
- Java 11: 2 초
- Kotlin (JVM): 2 초
- Java 15: 2 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호