0. (포드-풀커슨 알고리즘)
1. 에드몬드-카프 알고리즘
2. 디닉 알고리즘 (추가예정)
1. 에드몬드-카프 알고리즘
https://www.acmicpc.net/problem/6086
6086번: 최대 유량
첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위
www.acmicpc.net
기본문제, 알파벳으로 주어지는 정점의 번호만 잘 처리해주면 된다.
https://www.acmicpc.net/problem/2188
2188번: 축사 배정
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해
www.acmicpc.net
이분매칭 알고리즘으로 푸는게 더 간단하다.
https://www.acmicpc.net/problem/17412
17412번: 도시 왕복하기 1
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다.
www.acmicpc.net
https://www.acmicpc.net/problem/2316
2316번: 도시 왕복하기 2
N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방
www.acmicpc.net
Tip : 정점을 분할해야 한다
https://www.acmicpc.net/problem/7616
7616번: 교실로 가는 길
각 테스트 케이스마다 "Case #:" 형식으로 케이스 번호를 출력한다. 그 다음, K개의 겹치지 않는 경로 (1번에서 출발해 2번으로 도착하는 경로)가 존재하면 K개 줄에 각 경로를 출력한다. 없는 경우
www.acmicpc.net
https://www.acmicpc.net/problem/5651
5651번: 완전 중요한 간선
입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1<=K<=15)가 주어진다. 각 테스트 케이스에는 N, M (2 <= N <= 300; 2 <= M <= 5,000)가 주어지고 각각 정점의 수와 간선의 수
www.acmicpc.net
https://www.acmicpc.net/problem/11495
11495번: 격자 0 만들기
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각
www.acmicpc.net
https://www.acmicpc.net/problem/10319
10319번: 좀비 아포칼립스
때는 2020년, 당신과 그 일행은 좀비로 황폐화된 대도시의 어느 마을 안에 갇혔다. 당신들 또한 바이러스에 감염되었기 때문에 좀비가 되기 전에 빨리 병원을 찾아 치료해야 한다. 당신들은 과학
www.acmicpc.net
2. 디닉 알고리즘 (추가예정)
'자료구조 + 알고리즘' 카테고리의 다른 글
| 이분매칭 (Bipartite Matching) (0) | 2021.09.14 |
|---|---|
| SCC (강결합요소) (0) | 2021.09.14 |
| 최단거리 알고리즘 (0) | 2021.09.14 |
| 최소비용 신장트리 (0) | 2021.09.14 |
| BFS (너비우선탐색) (0) | 2021.09.14 |