유통전문회사 코코아상사의 오너인 커미는 새로운 사업 아이템을 구상하기 위해

전문경영인(CEO)인 하니에게 회사의 경영을 부탁하였다.

"코코아상사"는 직원들을 여러 개의 팀 단위로 조직을 구성하고 있으며 아래 그림은 CEO를 포함하여

10명의 직원과 4개의 팀으로 구성되어 있는 회사 조직도를 보여주고 있다.

그림의 조직도를 설명하면 다음과 같다.

1. 그림의 각 원들은 각각의 직원 1명을 표시하고 있으며,

CEO를 포함하여 총 10명의 직원을 표시하고 있다.

2. 원 안에 적힌 두 개의 숫자는 직원의 정보를 담고 있다.

왼쪽 숫자는 직원번호로 직원을 식별할 수 있도록 1번부터 순서대로 발급되는 일련번호이며,

오른쪽 숫자는 해당 직원의 하루 평균 매출액을 나타낸다.

위 그림에서 1번 직원은 14원을, 9번 직원은 28원의 하루 평균 매출액을 기록하고 있다.

3. CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며

그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있다.

화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 쪽의 직원은 팀원을 의미한다.

3-1. 직원번호 1번 은 회사의 CEO로 고정되어 있으며,

CEO는 항상 팀장이고 팀원일 수 없어 화살표를 받는 쪽이 될 수 없다.

3-2. 반면에 CEO를 제외한 나머지 모든 직원들은 다른 누군가로부터 정확히 1개의 화살표를 받게 된다.

3-3. 한 직원은 최대 2개의 팀에 소속될 수 있다. 만약 어떤 직원이 두 개의 팀에 소속되어 있다면,

반드시 하나의 팀에서는 팀장, 나머지 팀에서는 팀원이어야 한다.

팀장을 겸임하거나, 두 개의 팀에서 팀원이 될 수는 없다.

예를 들어 10번 직원은 D팀의 팀장이면서 동시에 5번 직원이 팀장으로 있는 C팀에 속한 팀원이다.

3-4. 5번, 9번, 10번 직원은 받는 쪽의 화살표와

시작하는 화살표가 모두 있으므로 팀장인 동시에 팀원이다.

3-5. 2번, 3번, 4번, 6번, 7번, 8번 직원은 시작하는 화살표가 없고

받는 쪽의 화살표만 있으므로 팀장이 아니며 오직 팀원이다.

3-6. 1번 직원인 CEO는 받는 쪽의 화살표가 없고

시작하는 화살표만 있으며 항상 님원이 아닌 팀장이다.

3-7. 그림의 조직도에는 A, B, C, D 총 34개의 팀이 존재하며,

각각 1번, 9번, 5번, 10번 직원이 팀장 직위를 담당하게 된다.

커미는 자신이 구상한 새로운 사업 아이템에 대해 직원들에게 설명하고자 하루 일정으로 워크숍을

계획하고 있다. 단, 모든 직원을 참석시킬 수 없어 아래와 같은 기준으로 워크숍에 참석할

직원들을 선발하려고 한다.

1. 워크숍에서 교육받은 내용은 전 직원들에게 공유되어야 하므로 모든 팀은 최소 1명 이상의

직원을 워크숍에 참석시켜야 한다.

2. 워크숍 기간동안, 회사의 매출 손실을 최소하화는 것이 중요하므로 워크숍에 참석하는 직원들의

하루평균 매출액의 합이 최소가 되어야 한다.

위 그림의 조직도에서 회색으로 색칠된 1번, 7번, 10번 직원을 워크숍에 참석시키면 모든 팀에서 최소

한명 이상의 직원을 참석시킨 것이 되며, 해당 직원들의 하루평균 매출액의 합은 44(14 + 13 + 17)원 이다.

10번 직원은 C팀과 D팀 모두에 속해 있으므로, 두 팀에서 모두 참석한 것으로 인정된다.

직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열

links가 매개변수로 주어진다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서,

참석하는 직원들의 하루 평균 매출액의 합을 최소로 하려고 한다.

그렇게 최소화된 매출액의 합을 구하는 프로그램을 작성하시오.

워크샵 timer 5s memory 256MB

워크샵 5s 256MB