전력망

시간 제한1초메모리 제한128 MB

요약

발전, 소비, 중계 노드와 용량 제한이 있는 네트워크에서 최대 유량 문제로 환원해 최대 총 소비량을 구합니다.

난이도: 보통10점 중 6점
유형: 그래프, 수학
정답자: 아직 제출이 없습니다

문제

전력망은 여러 노드(발전소, 소비자, 중계기)가 송전선으로 연결되어 이루어진다. 노드 $u$ 는 전력 $s(u) \ge 0$ 을 공급받을 수 있고, 전력 $0 \le p(u) \le p_{\max}(u)$ 을 생산할 수 있으며, 전력 $0 \le c(u) \le \min(s(u), c_{\max}(u))$ 을 소비할 수 있고, 전력 $d(u) = s(u) + p(u) - c(u)$ 을 송출할 수 있다. 다음 제약이 적용된다. 발전소는 $c(u) = 0$ , 소비자는 $p(u) = 0$ , 중계기는 $p(u) = c(u) = 0$ 이다. 노드 $u$ 에서 노드 $v$ 로 가는 송전선 $(u, v)$ 은 최대 한 개만 존재하며, 이 선은 $u$ 가 송출한 전력을 $0 \le l(u, v) \le l_{\max}(u, v)$ 만큼 $v$ 로 전달한다. 전력망에서 소비되는 총 전력을 $Con = \sum_u c(u)$ 라고 하자. $Con$ 의 최댓값을 구하여라.

u	종류	s(u)	p(u)	c(u)	d(u)
0	발전소	0	4	0	4
1		2	2	0	4
3	소비자	4	0	2	2
4		5	0	1	4
5		3	0	3	0
2	중계기	6	0	0	6
6		0	0	0	0

그림 1. 전력망의 예.

위 예시는 전력망의 유효한 상태 하나를 나타낸다. 발전소 $u$ 의 라벨 $x/y$ 는 $p(u) = x$ 이고 $p_{\max}(u) = y$ 임을 뜻한다. 소비자 $u$ 의 라벨 $x/y$ 는 $c(u) = x$ 이고 $c_{\max}(u) = y$ 임을 뜻한다. 송전선 $(u, v)$ 의 라벨 $x/y$ 는 $l(u, v) = x$ 이고 $l_{\max}(u, v) = y$ 임을 뜻한다. 이 상태에서 소비되는 전력은 $Con = 6$ 이다. 다른 상태들도 가능하지만 $Con$ 은 결코 6을 넘을 수 없다.

입력

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 하나의 전력망을 나타낸다. 각 집합은 네 개의 정수로 시작한다. 노드 수 $0 \le n \le 100$ , 발전소 수 $0 \le n_p \le n$ , 소비자 수 $0 \le n_c \le n$ , 송전선 수 $0 \le m \le n^2$ 이다.

이어서 (u,v)z 형태의 삼중쌍이 $m$ 개 주어진다. 여기서 $u$ 와 $v$ 는 노드 번호(0부터 시작)이고, $0 \le z \le 1000$ 은 $l_{\max}(u, v)$ 의 값이다.

이어서 (u)z 형태의 이중쌍이 $n_p$ 개 주어진다. 여기서 $u$ 는 발전소의 번호이고, $0 \le z \le 10000$ 은 $p_{\max}(u)$ 의 값이다.

마지막으로 (u)z 형태의 이중쌍이 $n_c$ 개 주어진다. 여기서 $u$ 는 소비자의 번호이고, $0 \le z \le 10000$ 은 $c_{\max}(u)$ 의 값이다.

모든 입력 수는 정수이다. 공백을 포함하지 않는 (u,v)z 삼중쌍과 (u)z 이중쌍을 제외하면, 입력 곳곳에 공백이 자유롭게 나타날 수 있다. 입력은 파일 끝에서 종료되며 항상 올바르다.

출력

각 데이터 집합마다, 해당 전력망에서 소비할 수 있는 전력의 최댓값을 한 줄에 하나씩 출력한다. 모든 결과는 정수이며 각각 새로운 줄의 처음부터 출력한다.

예제3

예제 1

입력

2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7
         (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5
         (0)5 (1)2 (3)2 (4)1 (5)4

예상 출력

15
6

예제 2
입력
```
0 0 0 0
```
예상 출력
```
0
```
예제 3
입력
```
2 1 1 1 (0,1)5 (0)10 (1)10
```
예상 출력
```
5
```