레이팅 미적용농장을 탈출한 베시(Bessie)는 아무존 강을 따라 여행사를 차리기로 했다. 강 양쪽에는 여러 관광지가 있으며, 각 관광지에는 얼마나 흥미로운지를 나타내는 정수 값이 매겨져 있다.
관광지들은 강을 건너는 경로로 연결되어 있다 (즉, 강의 같은 쪽에 있는 관광지끼리 연결하는 경로는 없다). 베시는 고객들을 위한 여행 코스를 설계하려 하며 당신의 도움이 필요하다. 여행 코스는 인접한 관광지들이 경로로 연결된 관광지들의 나열이다. 고객들에게 최상의 서비스를 제공하기 위해, 베시는 방문하는 각 관광지의 값의 합을 최대화하는 코스를 찾고 싶어 한다.
하지만 베시는 이런 여행 코스 여러 개를 동시에 운영할 수도 있다. 따라서 한 코스의 어떤 두 경로도 교차하지 않는 것이 중요하다. 두 경로 (a <-> x)와 (b <-> y)는 (a < b이고 y < x) 또는 (b < a이고 x < y) 또는 (a = b이고 x = y)일 때, 그리고 그때만 교차한다.
베시의 여행사를 위한 최상의 코스를 찾는 것을 도와주자. 베시는 아무존 강 어느 쪽의 어느 관광지에서든 시작하고 끝낼 수 있다.
첫째 줄: 공백으로 구분된 세 정수 N (1 <= N <= 40,000), M (1 <= M <= 40,000), R (0 <= R <= 100,000)이 주어지며, 각각 강 왼쪽의 관광지 수, 강 오른쪽의 관광지 수, 경로의 수를 나타낸다.
둘째 줄부터 N+1번째 줄까지: (i+1)번째 줄에 강 왼쪽의 i번째 관광지의 값을 나타내는 정수 L_i (0 <= L_i <= 40,000)가 주어진다.
N+2번째 줄부터 N+M+1번째 줄까지: (i+N+1)번째 줄에 강 오른쪽의 i번째 관광지의 값을 나타내는 정수 R_i (0 <= R_i <= 40,000)가 주어진다.
N+M+2번째 줄부터 N+M+R+1번째 줄까지: 각 줄에 공백으로 구분된 두 정수 I (1 <= I <= N)와 J (1 <= J <= M)가 주어지며, 강 왼쪽의 관광지 I와 강 오른쪽의 관광지 J 사이에 양방향 경로가 있음을 나타낸다.
여행 코스에서 얻을 수 있는 값의 합의 최댓값을 나타내는 정수 하나.
route.in · 출력을 쓸 파일 route.out3 2 4
1
1
5
2
2
1 1
2 1
3 1
2 28Output details: The optimal tour goes from site 1 on the left, to site 1 on the right, and ends at site 3 on the left, with values 1, 2, and 5 giving total 8.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > February > Gold