자답합니다.
플로우 하나를 더 보낼 수 있는 지 체크할 때
"인덱스가 더 작은"과 같은 비교는 WA를 받습니다.
인덱스가 더 작은 노드들을 경유하는 경로가
고려되지 못 하기 때문으로 생각됩니다.
용량을 0으로 만드는 테크닉을 통해
역으로 플로우가 흐르더라도 사전순으로 앞서는 노드의
플로우가 교체되지 않도록 하는 것이 가능합니다.
1031번 - 스타 대결
자답합니다.
플로우 하나를 더 보낼 수 있는 지 체크할 때
"인덱스가 더 작은"과 같은 비교는 WA를 받습니다.
인덱스가 더 작은 노드들을 경유하는 경로가
고려되지 못 하기 때문으로 생각됩니다.
용량을 0으로 만드는 테크닉을 통해
역으로 플로우가 흐르더라도 사전순으로 앞서는 노드의
플로우가 교체되지 않도록 하는 것이 가능합니다.
댓글을 작성하려면 로그인해야 합니다.
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열 순입니다.
도움 주시면 감사하겠습니다.