COCI 2014/2015 Contest #4 4번- 매직펌프 > 문제은행 : 정보올림피아드&알고리즘




2905 : 매직펌프

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
28 회   
시도횟수
42 회   

문제

여러 개의 농장을 운영하는 농부 경원이는 가뭄으로 물이 부족해지자 자신의 농장들에 물을 공급할 계획을 세웠다. 가뭄을 대비하여 아주 큰 저수지를 관리해왔으며 저수지에는 물이 충분히 있다고 한다.



문제는 저수지로부터 떨어져 있는 각 농장들에 물을 어떻게 공급할 것인가? 하는 것이다. 각 농장들은 저수지와의 거리도 제각각이고 고도(일부 농장은 저수지보다 고도가 높을 수 있다고 한다.) 또한 서로 달라서 수로나 배관만 설치하는 것으로는 물을 공급할 수 없다고 한다. 따라서 농장과 저수지 사이에 여러 개의 중계지와 배관을 건설하고 중계지와 중계지 사이 또는 중계지와 농장 사이 배관에 펌프를 설치하여 다음 중계지 또는 농장에 물을 공급하기로 하였다.



아래 예를 보자.

저수지로부터 1번 중계지에 12L의 물이 보내졌다.

1번 중계지에서 2번 중계지로 12L의 30%가, 3번 중계지로 12L의 70%가 보내졌다.

따라서 2번 중계지에는 3.6L가 있을 것이고 3번 중계지에는 8.4L가 있을 것이다.

4번과 5번은 농장이고 각각 3.6L, 8.4L의 물을 공급받게 된다.



 

그런데 몇몇 중계지와 중계지 사이의 펌프는 매직펌프라고 한다. 매직 펌프는 현재 보낼 수 있는 물의 양을 제곱한 만큼 보낼 수 있다고 한다. 위 그림에서 2번 중계지와 4번 농장사이의 배관에 설치된 펌프가 매직 펌프라고 한다면 최대 3.6 * 3.6 = 12.96L 까지 보낼 수 있게 된다..

매직 펌프에는 스위치가 달려있어 경원이가 원할 경우에는 그 기능을 켜거나 끌수 있다.



위 그림을 트리로 볼 때 각 중계지와 농장을 노드로 볼 수 있으며 단말노드가 농장이 된다.

물을 보내는 것은 그만큼의 비용이 들며 사업가인 경원이는 가능한 비용을 적게 쓰고자 한다.

노드와 노드 사이에 대한 정보와 농장노드에 대한 정보를 입력받아 경원이가 사용해야 하는 물의 최소양을 구하는 프로그램을 작성하시오.


입력형식

첫 행에 노드의 개수 N ( 1 ≤ N ≤ 1,000)이 입력된다.
이어서 N-1개의 행에 노드사이의 정보 Ai, Bi, Xi, Ti ( 1≤Ai, Bi≤N,  1≤Xi≤100, 0≤Ti≤1)가 입력된다. Ai, Bi는 노드 번호 이고 Xi는 백분율로서 Ai에 있는 물 Xi퍼센트를 Bi로 보낸다.
Ti가 1인 경우 매직 펌프, 0인 경우는 일반펌프이다.
다음 행에 N개의 정수 Ki(-1 또는 1 ≤ Ki ≤ 10)가 공백을 구분하여 입력된다.
Ki가 -1인 경우 중계지 이며 1 ≤ Ki ≤ 10인 경우 농장이고 Ki는 농장에서 필요로 하는 물의 양이다.


출력형식

첫 행에 경원이가 사용해야 하는 물의 최소 양을 소수 이하 4자리까지 출력한다.
결과값은 20억 이내이다..
출력 형식은 자유이나 출력 결과와 정답과의 차이가 0.001이하 이어야 정답으로 인정한다.


입력 예

5
1 2 50 0
1 3 50 0
2 4 25 0
2 5 75 1
-1 -1 4 1 9

출력 예

8.0000

입력 예

3
1 2 20 1
1 3 80 1
-1 4 8

출력 예

10.0000

입력 예

6
1 2 100 1
2 3 20 0
2 4 20 0
2 5 60 0
4 6 100 1
-1 -1 1 -1 1 2

출력 예

2.6591


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP