amok   11달 전



두 개의 수들의 집합 S와 T가 주어져 있을 때, S와 T의 매칭(matching)은 다음 조건을 만족하는
(s,t) ϵ SxT들의 집합이다.
조건: S의 각 원소( 원소 값의 범위 : 0<= a <= 100,000 )는 T의 적어도 한 원소와 쌍으로 되어야
한다. 그리고 T의 각 원소( 원소 값의 범위는 0<= b <= 100,000 )는 S의 적어도 한 원소와 쌍으
로 되어야 한다.
예를 들어 S={2,8,9,10,11}, T={0,3,4,6,7,11}일 때, M={(2,0), (2,3), (2,4), (8,6), (9,7), (10,11), (11,11)}은
S와 T의 매칭이고, M={(2,0), (8,3), (9,4), (10,6), (11,7)}은 S와 T의 매칭이 아니다.
매칭의 비용은 각 쌍의 원소들 사이의 차이의 절대값의 합으로 정의된다. 위의 예에서 M의 비용
은 10이다.
주어진 두 수 집합에 대해, 최소 비용의 매칭을 구하는 프로그램을 작성하시오.


입력)
3 % 테스트 회수 1 <= T <= 10
5 5 % 첫 번째와 두 번째 집합의 원소의 개수 1<= n1, n2 <= 50000
2 8 9 10 11 % 첫 번째 집합의 원소, 증가하는 순서로 나열됨
7 8 10 11 12 % 두 번째 집합의 원소, 증가하는 순서로 나열됨
9 8
2 8 9 10 11 20 22 23 30
2 9 10 11 12 13 22 30
5 6
2 8 9 10 11
0 3 4 6 7 11


출력)
(2,7), (8,8), (9,10), (10,10), (11,11), (11,12) : 7 % 매칭과 비용
(2,2), (8,9), (9,9), (10,10), (11,11), (11,12), (11,13), (20,22), (22,22), (23,22), (30,30) : 7
(2,0), (2,3), (2,4), (8,6), (9,7), (10,11), (11,11) : 10






어떻게 풀어야 할 지 모르겠네요

제가 전혀 모르는 알고리즘을 쓰기라도 하는 건지...

amok   11달 전

사실 BOJ에도 있는 문제였네요. 감사합니다.

amok   11달 전

논문 링크가 지금은 작동하지 않는데 그 논문을 지금 볼 방법은 없나요?

amok   11달 전

고맙습니다.

댓글을 작성하려면 로그인해야 합니다.