https://www.acmicpc.net/problem/2316
- 2월동안 187문제 풀기(지난달 누적 87개) (58/187)
- 한 세트로 풀어본 도시 왕복하기 1/2
- 어제 공부한 Dinic 알고리즘을 한번 보면서 써보고, 다시 외운 상태로 써보는 연습을 해봄
- 그래프 문제에서 관건은 결국 그래프 모델링임
- 열혈강호와 같은 업무 배분의 문제는 이분매칭, 즉 flow 문제로 환원 가능
- 간선을 한번만 지날 수 있는 경로의 수 찾기 문제는 flow 문제로 환원 할 수 있음
- 간선을 한번만 지나야 한다거나 등의 상한이 있다면 Demand로 해석 가능. Demand가 있는 Node는 Inner Source와 Inner Sink를 만들어서 edge에 cap을 넣어주면 됨.
1 |
|