Informatica Online Judge

  콩밭을 산책하는 콩충2 (Large) [2217 / 08A9]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 3   Total Tried : 3


The Champion of this Problem (C++) : gs16079 - 50ms / 4623byte
My Best Submission (C++) : N/A

[34th 이윤상]
Writer ID : [gs16079]

Background

윤상 왕국의 문제를 "이산구조" 친구들은 아무도 풀어주지 않았다. 문제는 심각해졌고 윤상은 새로운 정책을 떠올렸다. 상황은 다음과 같다.

윤상이 다스리는 왕국에는 N개의 영지가 있는데 두 귀족 민형과 정용이 나누어 관리하고 있다.
임의의 두 영지 사이에는 윤상의 애완동물, 콩충이 따먹을 수 있는 조성되지 않은 콩밭이 있다.
두 영주들은 각각 자신들의 영지를 한 번씩만 방문하면서 총 따먹을 수 있는 콩의 양이 최대가 되게끔 산책로를 조성해두었다.
두 영주들은 단순해서 가장 콩이 많은 콩밭부터 차례대로 채택하면서 산책로를 만들었다.
민형과 정용의 산책로 사이에는 콩밭이 없기 때문에 전세기로 이동해야하는데, 이는 비용이 상당히 많이 든다.
따라서 두 산책로를 잇는 콩밭을 하나 조성하였다. 물론, 콩의 개수가 가장 많은 콩밭을 택하였다.

원래는 영지의 국유화를 통해 두 귀족간의 세력을 견제하고자 하였으나 백지로 돌아갔다.
윤상의 새로운 정책은 바로 두 귀족간의 세력 불균형을 해소하는 것이다.

위에서 조성된 산책로에서 A영지에서 B영지로 가는 길은 유일하다.
따라서 두 영지 사이의 거리를 "지나야하는 콩밭의 콩의 개수의 총합"으로 정의하였을 때, 가장 거리가 먼 두 영지가 바로 무역의 중심지이다.
이 두 영지를 한 사람이 독식하면 서로 간의 적절한 견제가 이루어지지 못할 것이다.
따라서 윤상은 한 사람이 두 무역의 중심지를 독식하고 있다면 ‘뒤의 번호의 영지’를 다른 사람의 일반 영지와 교환시킬 것이다.
물론 하나씩 사이좋게 나눠가졌다면 그저 흐뭇하게 바라보기만 할 것이다.

당신은 윤상 바라기이다. 다시 말하면, 윤상의 정책에 무조건적으로 동의하는 사람이다. 정책을 대신 시뮬레이션해서 결과를 알려주자.

Input

첫 번째 줄에 영지의 수 N(4 <= N <= 1000)과 민형의 영지의 수 K(1 < K < N)이 주어진다. 영지는 1부터 N까지 고유의 번호가 붙어있다.
두 번째 줄부터 N줄에 걸쳐 N*N의 인접행렬이 주어진다. i행 j열은 I영지와 j영지 사이 콩의 개수를 의미한다. 콩의 개수는 1 이상 1000000이하이고 서로 다른 콩밭의 콩의 개수는 전부 다르다.
N+2번째 줄에는 민형의 영지 번호가 오름차순으로 K개 주어진다.
N+3번째 줄에는 정용의 영지 번호가 오름차순으로 N-K개 주어진다.

Subtask Info

#2. 4 <= N <= 1000

Output

민형의 ‘무역의 중심 영지’ 번호와 정용의 ‘무역의 중심 영지’ 번호를 공백을 사이에 두고 출력한다.

(단, 무역의 중심 영지 한 쌍은 유일하다.)

IO Example

입출력예시 1

입력
4 2
0 6 7 8
6 0 9 10
7 9 0 11
8 10 11 0
1 3
2 4

출력
28
1 2

해설
민형의 콩밭은 7이고 정용의 콩밭은 10이다. 3-4를 잇는 콩의 개수가 11으로 가장 많고 이를 다 더하면 28이다.
1-3-4-2로 산책로가 연결되고 1과 2가 무역의 중심지가 된다.

입출력예시 2

입력
6 3
0 100 98 1 8 2
100 0 99 6 12 9
98 99 0 7 11 10
1 6 7 0 4 3
8 12 11 4 0 5
2 9 10 3 5 0
4 5 6
1 2 3

출력
220
3 1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]