caffeinism7   2년 전

graph.png

다음과 같이 그래프를 조정한 뒤 s에서 나가는 간선의 용량을 지민 팀의 가능 경기수로, e로 들어오는 간선을 한수 팀의 가능 경기수로 지정 한뒤 나머지 가운데 간선은 용량을 모두 1로 지정했습니다.

그리고 사전순으로 정렬을 할 방법을 곰곰히 생각하다가 이런 weight표를 사용했습니다.

...

512 256 128 64 32

16 8 4 2 1

오른쪽 아래에 1이오고 가장 왼쪽 위에는 2^(nm)이 오는 weight표입니다. 2의 승수이므로 당연히 선택한 간선 다음에 나오는 모든 간선을 더해도 선택한 간선보다 더 높은 가중치를 가질수는 없으니 Min-Cost Max-Flow 사용시 정상적으로 정렬된 그래프를 출력합니다.

하지만 안타깝게도 n*m=최대 2500이기 때문에 일반적으로는 이 방법을 사용할 수 없어 2^2500 이상을 표현할 수 있는 자료형(400Byte)을 하나 정의하여 사용하였습니다.

2 * (50 + 50 * 50 + 50) = 5200개의 간선의 가중치만 저장하면 되고 부차 다른데 사용되는 BigInt를 합쳐도 10000개가 되지 않을것이라는 생각으로 코드를 짰는데 50*50도 빠르게 출력되나 백준에 제출시 메모리 초과라는 에러가 나네요..

질문 검색을 해보니 나오는 답변은 어려워서 이해하기가 어렵고 답에 근접한 것 같은데 메모리에러 때문에 마음이 아픕니다.

다른 식으로 이 간선들의 적절한 weight를 지정하거나 이 답에 근접해 갈 수 있는 방법이 있을까요?

smu201111192   2년 전

long double로 weight를 주고 , mcmf 를 돌려보는건 어떨까요?

n*m이 너무커서 잘 될지는 모르겠지만 ㅠ

smu201111192   2년 전

실수 자료형으로 풀 수 있는 사전순 플로우 문제입니다. 

https://www.acmicpc.net/proble...

위 문제는 2^100까지만 구하면되서 weight를 long double로 주고 풀었던 기억이 있네요.

caffeinism7   2년 전

그것도 해봤으나 long double도 유효숫자가 저 큰 숫자들의 덧셈을 표현하기엔 턱없이 작기 때문에 제대로 작동하지 않더군요. 엄청나게 큰 숫자(2^2500)와 아주 작은숫자(1)을 더하는것을 생각해보면 작은 숫자가 유효숫자 범위에 들어가지 않아 증발하게 되어 의미가 없는 것 같습니다.

caffeinism7   2년 전

검색해보니 long double의 정밀도는 100비트를 조금 넘는다고 하네요. 그래서 2^100까지만 사용하는것은 가능한 것 같습니다.

smu201111192   2년 전

역시 안되는군요 ㅋ;

그럼 mcmf로 풀기는 좀 힘들 것같네요, 

flow를 흘릴 수 있는 만큼 흘린후, 포화그래프 상태에서 

그리디하게  플로우를 스왑해서 푸시는 방법밖에 없을 듯합니다.



caffeinism7   2년 전

혹시 관련 알고리즘 게시글이 있을까요? 초보라 모르는게 많네요. 사실 메모리 초과도 왜 나오는지 모르겠습니다. 128MB를 사용한것같지는 않은데..

smu201111192   2년 전

다른 게시글은 잘 모르겠네요.

질문 게시글 풀이에서 어떤부분이 이해가 안 되시나요?

caffeinism7   2년 전

사전순으로 더 높은 우선순위에 있도록 만들어 줄 수 있는 저 경로를 어떤 방식으로 찾으면 좋을까요?

smu201111192   2년 전

KakaoTalk_20171108_002806597.jpg

이런 그래프가 있다고 해볼게요. 1-1 매칭 2-2매칭 3-3 매칭

total flow =  max flow = 3 입니다.

[ 1 0 0

  0 1 0

 0 0 1 ]   

flow는 최대로 흘려서 , 가능한 대진표를 하나 찾았습니다. 

하지만 위 그래프는 사전으로 제일 빠른 대진표가 아닙니다.



smu201111192   2년 전

matching[][]

 [ 1 0 0

   0 1 0

  0 0 1 ]

사전순으로 빠른 그래프를 만들기 위해, matching[1][1] (Team1의 1번선수와 Team2의 1번선수가 경기를함)  0으로 바꿀 수 있나 확인해봅니다.

(Team2의 1번 정점)에서 시작해서, 빨강색 경로를 통해  다시 (Team2의 1번 정점으로 )돌아올 수 있습니다.

해당경로에 flow를 흘려주면, 최대유량은 그대로 유지되고 

 또한 (Team1 의 1번 )- (Team2의 1번)  ,    (Team1의 2번) -(Team2의 2번) 의 매칭이 상쇄되어 사라지고,

새로운  매칭 (Team1의 1번) - (Team2의 2번) , (Team1의 2번) -(Team2의 1번) 이 생기게됩니다.

[ 1 0 0                       [   0 1 0

   0 1 0          ------>       1 0  0

  0 0 1 ]                        0   0   1 ]


위과정을 반복적으로 수행하시면됩니다.


2.jpg







  

caffeinism7   2년 전

큰 도움이 됐습니다. 감사합니다.

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