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

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

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

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

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

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

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

역시 안되는군요 ㅋ;

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

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

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

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

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

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

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

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

total flow =  max flow = 3 입니다.

[ 1 0 0

  0 1 0

 0 0 1 ]   

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

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

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 ]

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

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