yanghj1490   1년 전

1031번 문제에 대한 도움을 구합니다.

AC로 소스 코드는 삭제합니다.

네트워크 플로우로 작성했습니다.

로직은 아래와 같습니다.

1. 최대 플로우 상태를 하나 구합니다.

2. 사전 순으로 더 앞에 올 수 있는 상태가 있으면, 교환합니다

1은 에드몬드 카프 알고리즘으로 구현했습니다.

2는 FlowSwap(i, j) 함수로 구현했는데, 

메커니즘은 아래와 같습니다 ( > 는 방향을 의미합니다 )

가. S > i > j > T 플로우를 제거합니다

나. S에서 플로우를 하나 흘립니다.

나-1). 이때 i와 i보다 사전순으로 앞서는 노드는 방문하지 않습니다.

나-2). 이때 j보다 사전순으로 앞서는 노드는 방문하지 않습니다.(단, i > j의 경우는 j를 방문하지 않습니다.)

다. 싱크에 도달하면 교체하고, 도달하지 못하면 복구합니다.

FlowSwap하는 순서는

1행 1열 > M열

2행 1열 > M열

...

N행 1열 > M열 순입니다.


도움 주시면 감사하겠습니다.

yanghj1490   1년 전

자답합니다.

플로우 하나를 더 보낼 수 있는 지 체크할 때

"인덱스가 더 작은"과 같은 비교는 WA를 받습니다.

인덱스가 더 작은 노드들을 경유하는 경로가

고려되지 못 하기 때문으로 생각됩니다.

용량을 0으로 만드는 테크닉을 통해

역으로 플로우가 흐르더라도 사전순으로 앞서는 노드의

플로우가 교체되지 않도록 하는 것이 가능합니다.

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