BOJ
-
BOJ_2188 축사Algorithm/BOJ 2018. 10. 23. 13:22
2188 축사 2188 축사https://www.acmicpc.net/problem/2188 분류네트워크 유량애드몬드-카프 알고리즘BFS이분 매칭 TIPS포드 - 풀거슨 알고리즘을 풀 때, v -> u로 가는 용량이 주어진다면, u -> v로 가는 용량 0의 간선을 만들어 주어야 한다.코드에서는 capacity[][] 배열을 사용해서 그래프를 나타내준다면, 초기값이 0이기 때문에 1번의 내용을 생각해줄 필요가 없다. 하지만 간선 찾는 시간을 단축시키기 위해 인접리스트로 그래프를 표현했다면, 꼭 인접리스트에 반대로 가는 가상의 간선을 만들어주어야한다. 처음부터 그래프를 배열로 했다면 상관없다.이분 매칭은 source와 sink가 여러개인 네트워크 유량문제에서 super source와 super sink를 ..
-
(BOJ)1504 특정한 최단경로Algorithm/BOJ 2018. 10. 4. 14:28
1504 특정한 최단 경로백준 특정한 최단 경로 Tip다익스트라 알고리즘 활용다익스트라 알고리즘은 출발점에서 모든 정점에 대한 최단거리를 구하는 알고리즘이다.꼭 들려야 하는 정점을 끝나는 지점으로 하는 다익스트라를 여러번 돌려 원하는 값을 찾을 수 있다. CODEximport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class BOJ_1504 { static final int INF = 800000; static List[] map; static int node; static int edge; public static void main(Strin..
-
(BOJ) 11657 타임머신Algorithm/BOJ 2018. 9. 24. 23:01
11657 타임머신 11657 타임머신https://www.acmicpc.net/problem/11657 Algorithm최단거리벨만 - 포드 알고리즘 CODEimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;public class BOJ_11657 { static int N; static int M; static int[] dist; static int[][] map; static ArrayList[] list; static BufferedR..