adh0463   6년 전

안녕하세요.

스타대결 1031 문제 풀고있는데요..ㅋㅋㅋ

아 진짜 플로우 바꿔주는 게 힘들어서 질문남겨요


정점 번호 부여한 것은 아래처림 햇구요

A팀의 정점 번호 : 0부터 N-1

B팀의 정점 번호 : N부터 N+M-1


57번 줄까지 우선 플로우를 흘립니다. 포드 풀커슨을 사용했구요, 제 생각엔 여기까진 문제 없다고 봐요

그리고 matched가 가능한 총 경기 수인데, 각 팀의 수를 만족하지 못하면 -1을 출력하고 종료합니다.

둘 다 만족한다면, 

1번 for문 : A팀의 u정점에 대해

2번 for문 : B팀의 v정점의 , u->v로 가는 데 잔여용량이 없을(매칭된) 때

3번 for문 : u보다 정점번호가 큰 A팀의 i 정점에서

4번 for문 : v보다 정점번호가 큰 B팀의 j정점을 찾고, 스왑할 수 없는 경우를 모두 제외합니다.

  예외 1. 정점 i와 정점 v가 매칭된 경우

  예외 2. 정점 u와 정점 j가 매칭된 경우

  예외 3. 정점 i와 정점 j가 매칭이 되지 않은 경우

정리하자면, 스왑경로를 정점 u->v가 매칭되어 있으며, i->j가 매칭되어 있고, u->j로 플로우를 흘릴 수 잇고, i->v로 플로우를 흘릴 수 있을 때 스왑하도록 했습니다.


제가 로직을 잘 못 짯나요..??

// 해결되면 일부 소스는 삭제하겟습니당

tjdwo5313   4년 전

저도 구현하고 보니 글쓴이 님과 비슷하게

가능한 매칭을 구한 후 61-82줄처럼 그리디하게 스왑하는 식으로 풀려 하였습니다만

계속해서 틀렸다고 뜹니다 ㅠㅠ

(u, v)와 (i, j)를 그리디하게 스왑할 경우 사전순으로 앞서는 경우를 지나칠 가능성이 있는 것인가요?

아무리 생각해도 여러 단계를 거쳐서 플로우를 바꿔주는 것과 동일한 결과를 낼 것 같은데 혹시 힌트 주실 수 있으신가요 ㅠㅠㅠ

감사합니다...

adh0463   4년 전

다른 방식으로 해결했던 기억이 나네요.. 


플로우를 바꾸고자 근시적으로(이렇게 접근) 하면 안됐던 이유는 확실히 있었던 걸로 기억납니다.

제가 짰었던 소스가 두 매칭만 찾아서 플로우를 변경해주는 알고리즘이라면 더 큰 사이클(두 매칭뿐만 아니라 다른 요소들을 포함한)이 존재하여 그 사이클 내에서 플로우를 조절해야만 사전순으로 가장 앞서는 것을 가져올 수 있었던 걸로 기억이 나요..

화이팅입니다 :)

tjdwo5313   4년 전

감사합니다!!

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