algoshipda   1년 전

source와 1팀의 모든 선수간에 해당하는 승수만큼의 capacity를 가지는 간선을 추가했구요.

2팀의 모든 선수와 sink에도 해당하는 승수의 capacity로 간선을 만들어줬구요.

1팀과 2팀에의 각 선수는 상대팀의 모든 선수에게 capacity가 1인 간선이 생기도록 만들어줬습니다.

제 생각에 이렇게 하면 일단 1,2,3조건은 만족시킬 수 있을것 같은데

문제는 조건4를 어떤식으로 처리해야할지 모르겠습니다. 조그만 힌트라도 얻고 싶습니다.

pichulia   1년 전

일단 flow를 돌려서 정답을 하나 구해놓습니다.

그 다음에 해야할 일은?

flow 그래프가 유지되면서

a[i][j] == 1 이 최대한 늦게 등장하도록 흐름을 바꾸는 작업을 해야하는 거겠죠?


그럼 일단 if(a[i][j] == 1) 인 어떤 애에 대해서, 얘가 a[i][j] = 0이 되도록 바꿀 수 있는지를 알아보는 부분을 추가해야 합니다.


28ddbd08b4d79ff383bd40c8f2069b47.png

위의 그림은 a[s][e] = 1인 상황인데

얘를 어떻게 어떻게 빨간 선같은 경로를 잘 찾아서

flow는 똑같지만 a[s][e] = 0 이 되도록 만들 수 있습니다.


하도 옛날에 짜서 기억이 잘 안나는데...

저 사전순으로 앞서게 만들어주는 빨간 경로를 찾는게 아마 O(n^3)?O(n^2)? 쯤 걸릴거같고요

이를 n*n가지 애들에 대해 반복하면 (저 빨간 경로를 찾는 경우가 생각보다 많지 않아서) 시간내에 답이 나오게 됩니다....


뭐 추가적으로 한줄 적자면..

이 문제 같은 경우에는...사전순으로 가장 앞서는걸 한번에 뙇! 찾기보단..."현재 상황"보다 사전순으로 앞선거 "하나"만 대충 찾고, 이 작업을우다다닥 반복하다보면 사전순으로 가장 앞선 답이 딱 하고 나올것입니다... 이런 식으로 생각하면 코딩이 약간 더 쉬워질게용ㅋㅋㅋ

algoshipda   1년 전

감사합니다! 해볼게요

algoshipda   1년 전

pichulia

간신히 뚫었습니다 감사합니다!

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