https://www.acmicpc.net/problem/11375
- 2월동안 187문제 풀기(지난달 누적 87개) (31/187)
- 오늘 배운 Edmonds-karp 알고리즘. 유량 그래프에서 최대흐름/최소컷 찾기
adj[V][V]
모든 정점에 대한 양방향 인접 그래프cap[V][V]
모든 정점에 대한 유량 배열- 이번에 찾은 알고리즘은 CP-algorithm 출처
- 새로운 flow을 넣을 수 없을 때 까지 BFS 계속 시도
- 간선의 여부를 adj로 파악하고, 최소 cap을 찾아가면서 BFS함
- cap이 없다면 갈 수 없음.
- residue를 줄 것이기 때문에, 다른 간선을 줄이면서 전진하는게 가능
- Residual Network는 flow가 없다면 Capacity Network랑 같음
- flow가 생기면 반대 방향으로 residue를 반영해줌
- 근데 Bipartite Matching DFS로 그냥 푸는게 훠어얼씬 빠름.
1 |
|