13161번: 분단의 슬픔
첫 번째 줄에는 UCPC 구성원의 수 N(1 ≤ N ≤ 500)이 주어진다. 두 번째 줄에는 N개의 정수가 주어지는데, i번째 수가 1이면 i번 사람은 무조건 A진영에 들어가야 함을, 2라면 무조건 B진영에 들어가야
www.acmicpc.net
UCPC 2016에 출제된 flow 문제이다.
그래프가 크기 때문에 dinic 또는 그보다 빠른 flow 알고리즘이 필요하다.
워낙 유명한 문제이기에 풀이는 생략한다.
이 문제에서 dinic으로 TLE를 받는다면 다음 두 가지를 확인해보자.
첫 번째로 dfs 과정에서 매번 간선을 처음부터 확인하면 O(V^2 E)가 보장되지 않는다.
work 배열과 reference 변수를 이용하여 해결할 수 있는데 구글링하면 금방 찾을 수 있다.
두 번째로 cap과 flow는 인접 행렬로 관리해야 한다.
sparse graph에서는 구조체 구현이 빠르지만 dense graph에서는 인접 행렬 구현이 빠르다.
이 문제에서 구조체 구현은 TLE를 받는다.
끝
'일기' 카테고리의 다른 글
| Ghudegy 정품 키 (0) | 2023.04.30 |
|---|---|
| 자담치킨 신메뉴 티키타코 순살치킨 후기 (2) | 2023.04.28 |
| LzSeg 사용 시 주의 사항 (0) | 2023.04.11 |
| 2023년 4월 2일 일기 (0) | 2023.04.02 |
| 2023년 3월 24일 일기 (2) | 2023.03.24 |
