Algorithm
-
욕심쟁이 판다 - 1937Algorithm/BOJ 2020. 2. 25. 20:18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 //1937 - 욕심쟁이 판다 #include #include using namespace std; #define IMP -100000000 int N; vector arr; vector cache; int xarr[4] = {1, -1, 0, 0}; int yarr[4] = {0, 0, 1, -1}; void init() { cin >> N; arr = cache = vector(N+2, vector(N+2)); for(int i = 1; i arr[i]..
-
최대 유량 - 6086Algorithm/BOJ 2020. 2. 25. 00:21
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 //6086 - 최대 유량 #include #include #include using namespace std; #define MAX_V 52 #d..
-
Dinic's AlgorithmAlgorithm/그래프 2020. 2. 24. 21:03
http://blog.naver.com/kks227/220812858041 디닉 알고리즘(Dinic's Algorithm) (수정: 2016-09-19) 안녕하세요. 예고한 대로 더 빠른 시간복잡도의 최대 유량 알고리즘을 소개하러 왔습니다.그런데, 본래는 ... blog.naver.com kks227님의 디닉알고리즘 코드와 설명을 참고했습니다! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 ..
-
열혈강호 - 11375Algorithm/BOJ 2020. 2. 24. 00:08
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 //11375 - 열혈강호 #include #include using namespace std; int N, M; vector adj; vector aMatch, bMatch; vector visited; void init() { cin >> N >> M; adj = vector(N + 1, vector(M + 1, false)); int n; int from; for(int to = 1..
-
이분 매칭 문제를 해결하는 증가 경로 알고리즘Algorithm/그래프 2020. 2. 23. 22:22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 //이분 매칭 문제를 해결하는 증가 경로 알고리즘 //A와 B의 정점의 개수 int n, m; //adj[i][j] : Ai와 Bj가 연결되어 있는가? bool adj[MAX_N][MAX_M]; //각 정점에 매칭된 상대 정점의 번호를 저장한다 vector aMatch, bMatch; //dfs()의 방문 여부 vector visited; //A의 정점인 a에서 B의 매칭되지 않은 정점으로 가는 경로를 찾는다 bool dfs(int a) { if(visited[a]) return false; ..
-
발전소 - 1102Algorithm/BOJ 2020. 2. 23. 18:29
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 //1102 - 발전소 #include #include using namespace std; #define INF 2000000000 int N; int arr[16][16]; int fstate = 0; int cond; vector cache; void init() { cin >> N; for(int i = 0; i arr[i][j]; string s; cin >> s; for(int i = 0; i