1/*
2 * λ€νΈμν¬ νλ‘μ° (Network Flow)
3 * Ford-Fulkerson, Edmonds-Karp, μ΄λΆ 맀μΉ, μ΅μ μ»·
4 *
5 * κ·Έλνμμ μ΅λ μ λμ μ°Ύλ μκ³ λ¦¬μ¦μ
λλ€.
6 */
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11#include <limits.h>
12#include <stdbool.h>
13
14#define MAX_V 1001
15#define INF INT_MAX
16
17/* =============================================================================
18 * 1. Ford-Fulkerson (DFS κΈ°λ°)
19 * ============================================================================= */
20
21int capacity_ff[MAX_V][MAX_V];
22bool visited_ff[MAX_V];
23
24int dfs_ff(int u, int sink, int flow) {
25 if (u == sink) return flow;
26 visited_ff[u] = true;
27
28 for (int v = 0; v < MAX_V; v++) {
29 if (!visited_ff[v] && capacity_ff[u][v] > 0) {
30 int min_flow = (flow < capacity_ff[u][v]) ? flow : capacity_ff[u][v];
31 int result = dfs_ff(v, sink, min_flow);
32 if (result > 0) {
33 capacity_ff[u][v] -= result;
34 capacity_ff[v][u] += result;
35 return result;
36 }
37 }
38 }
39 return 0;
40}
41
42int ford_fulkerson(int source, int sink, int n) {
43 int max_flow = 0;
44 int flow;
45
46 while (1) {
47 memset(visited_ff, false, sizeof(visited_ff));
48 flow = dfs_ff(source, sink, INF);
49 if (flow == 0) break;
50 max_flow += flow;
51 }
52
53 return max_flow;
54}
55
56/* =============================================================================
57 * 2. Edmonds-Karp (BFS κΈ°λ°, O(VEΒ²))
58 * ============================================================================= */
59
60typedef struct {
61 int** capacity;
62 int** flow;
63 int n;
64} FlowNetwork;
65
66FlowNetwork* fn_create(int n) {
67 FlowNetwork* fn = malloc(sizeof(FlowNetwork));
68 fn->n = n;
69 fn->capacity = malloc(n * sizeof(int*));
70 fn->flow = malloc(n * sizeof(int*));
71 for (int i = 0; i < n; i++) {
72 fn->capacity[i] = calloc(n, sizeof(int));
73 fn->flow[i] = calloc(n, sizeof(int));
74 }
75 return fn;
76}
77
78void fn_free(FlowNetwork* fn) {
79 for (int i = 0; i < fn->n; i++) {
80 free(fn->capacity[i]);
81 free(fn->flow[i]);
82 }
83 free(fn->capacity);
84 free(fn->flow);
85 free(fn);
86}
87
88void fn_add_edge(FlowNetwork* fn, int u, int v, int cap) {
89 fn->capacity[u][v] += cap;
90}
91
92int edmonds_karp(FlowNetwork* fn, int source, int sink) {
93 int max_flow = 0;
94 int* parent = malloc(fn->n * sizeof(int));
95 int* queue = malloc(fn->n * sizeof(int));
96
97 while (1) {
98 memset(parent, -1, fn->n * sizeof(int));
99 parent[source] = source;
100
101 /* BFS */
102 int front = 0, rear = 0;
103 queue[rear++] = source;
104
105 while (front < rear && parent[sink] == -1) {
106 int u = queue[front++];
107 for (int v = 0; v < fn->n; v++) {
108 if (parent[v] == -1 &&
109 fn->capacity[u][v] - fn->flow[u][v] > 0) {
110 parent[v] = u;
111 queue[rear++] = v;
112 }
113 }
114 }
115
116 if (parent[sink] == -1) break;
117
118 /* κ²½λ‘ μ μ΅μ μ©λ μ°ΎκΈ° */
119 int path_flow = INF;
120 for (int v = sink; v != source; v = parent[v]) {
121 int u = parent[v];
122 int residual = fn->capacity[u][v] - fn->flow[u][v];
123 if (residual < path_flow) path_flow = residual;
124 }
125
126 /* μ λ μ
λ°μ΄νΈ */
127 for (int v = sink; v != source; v = parent[v]) {
128 int u = parent[v];
129 fn->flow[u][v] += path_flow;
130 fn->flow[v][u] -= path_flow;
131 }
132
133 max_flow += path_flow;
134 }
135
136 free(parent);
137 free(queue);
138 return max_flow;
139}
140
141/* =============================================================================
142 * 3. μ΄λΆ λ§€μΉ (Bipartite Matching)
143 * ============================================================================= */
144
145typedef struct {
146 int** adj;
147 int* adj_size;
148 int* match_left;
149 int* match_right;
150 bool* visited;
151 int left_n;
152 int right_n;
153} BipartiteGraph;
154
155BipartiteGraph* bg_create(int left_n, int right_n) {
156 BipartiteGraph* bg = malloc(sizeof(BipartiteGraph));
157 bg->left_n = left_n;
158 bg->right_n = right_n;
159 bg->adj = malloc(left_n * sizeof(int*));
160 bg->adj_size = calloc(left_n, sizeof(int));
161 for (int i = 0; i < left_n; i++) {
162 bg->adj[i] = malloc(right_n * sizeof(int));
163 }
164 bg->match_left = malloc(left_n * sizeof(int));
165 bg->match_right = malloc(right_n * sizeof(int));
166 bg->visited = malloc(right_n * sizeof(bool));
167 memset(bg->match_left, -1, left_n * sizeof(int));
168 memset(bg->match_right, -1, right_n * sizeof(int));
169 return bg;
170}
171
172void bg_free(BipartiteGraph* bg) {
173 for (int i = 0; i < bg->left_n; i++) {
174 free(bg->adj[i]);
175 }
176 free(bg->adj);
177 free(bg->adj_size);
178 free(bg->match_left);
179 free(bg->match_right);
180 free(bg->visited);
181 free(bg);
182}
183
184void bg_add_edge(BipartiteGraph* bg, int left, int right) {
185 bg->adj[left][bg->adj_size[left]++] = right;
186}
187
188bool bg_dfs(BipartiteGraph* bg, int u) {
189 for (int i = 0; i < bg->adj_size[u]; i++) {
190 int v = bg->adj[u][i];
191 if (bg->visited[v]) continue;
192 bg->visited[v] = true;
193
194 if (bg->match_right[v] == -1 || bg_dfs(bg, bg->match_right[v])) {
195 bg->match_left[u] = v;
196 bg->match_right[v] = u;
197 return true;
198 }
199 }
200 return false;
201}
202
203int bipartite_matching(BipartiteGraph* bg) {
204 int matching = 0;
205
206 for (int u = 0; u < bg->left_n; u++) {
207 memset(bg->visited, false, bg->right_n * sizeof(bool));
208 if (bg_dfs(bg, u)) {
209 matching++;
210 }
211 }
212
213 return matching;
214}
215
216/* =============================================================================
217 * 4. νΈνν¬λ‘ννΈ-μΉ΄ν (Hopcroft-Karp, O(EβV))
218 * ============================================================================= */
219
220int* dist_hk;
221int* match_left_hk;
222int* match_right_hk;
223int** adj_hk;
224int* adj_size_hk;
225int left_n_hk, right_n_hk;
226
227bool hk_bfs(void) {
228 int* queue = malloc((left_n_hk + 1) * sizeof(int));
229 int front = 0, rear = 0;
230
231 for (int u = 0; u < left_n_hk; u++) {
232 if (match_left_hk[u] == -1) {
233 dist_hk[u] = 0;
234 queue[rear++] = u;
235 } else {
236 dist_hk[u] = INF;
237 }
238 }
239
240 bool found = false;
241 while (front < rear) {
242 int u = queue[front++];
243 for (int i = 0; i < adj_size_hk[u]; i++) {
244 int v = adj_hk[u][i];
245 int next = match_right_hk[v];
246 if (next == -1) {
247 found = true;
248 } else if (dist_hk[next] == INF) {
249 dist_hk[next] = dist_hk[u] + 1;
250 queue[rear++] = next;
251 }
252 }
253 }
254
255 free(queue);
256 return found;
257}
258
259bool hk_dfs(int u) {
260 for (int i = 0; i < adj_size_hk[u]; i++) {
261 int v = adj_hk[u][i];
262 int next = match_right_hk[v];
263 if (next == -1 || (dist_hk[next] == dist_hk[u] + 1 && hk_dfs(next))) {
264 match_left_hk[u] = v;
265 match_right_hk[v] = u;
266 return true;
267 }
268 }
269 dist_hk[u] = INF;
270 return false;
271}
272
273int hopcroft_karp(int left_n, int right_n, int** adj, int* adj_size) {
274 left_n_hk = left_n;
275 right_n_hk = right_n;
276 adj_hk = adj;
277 adj_size_hk = adj_size;
278
279 dist_hk = malloc(left_n * sizeof(int));
280 match_left_hk = malloc(left_n * sizeof(int));
281 match_right_hk = malloc(right_n * sizeof(int));
282
283 memset(match_left_hk, -1, left_n * sizeof(int));
284 memset(match_right_hk, -1, right_n * sizeof(int));
285
286 int matching = 0;
287 while (hk_bfs()) {
288 for (int u = 0; u < left_n; u++) {
289 if (match_left_hk[u] == -1 && hk_dfs(u)) {
290 matching++;
291 }
292 }
293 }
294
295 free(dist_hk);
296 free(match_left_hk);
297 free(match_right_hk);
298 return matching;
299}
300
301/* =============================================================================
302 * 5. μ΅μ μ»· (Min Cut)
303 * ============================================================================= */
304
305void find_min_cut(FlowNetwork* fn, int source, int* reachable, int* cut_size) {
306 bool* visited = calloc(fn->n, sizeof(bool));
307 int* queue = malloc(fn->n * sizeof(int));
308 int front = 0, rear = 0;
309
310 visited[source] = true;
311 queue[rear++] = source;
312
313 *cut_size = 0;
314
315 while (front < rear) {
316 int u = queue[front++];
317 reachable[(*cut_size)++] = u;
318 for (int v = 0; v < fn->n; v++) {
319 if (!visited[v] && fn->capacity[u][v] - fn->flow[u][v] > 0) {
320 visited[v] = true;
321 queue[rear++] = v;
322 }
323 }
324 }
325
326 free(visited);
327 free(queue);
328}
329
330/* =============================================================================
331 * ν
μ€νΈ
332 * ============================================================================= */
333
334int main(void) {
335 printf("============================================================\n");
336 printf("λ€νΈμν¬ νλ‘μ° μμ \n");
337 printf("============================================================\n");
338
339 /* 1. Edmonds-Karp */
340 printf("\n[1] Edmonds-Karp μκ³ λ¦¬μ¦\n");
341 FlowNetwork* fn = fn_create(6);
342 fn_add_edge(fn, 0, 1, 16);
343 fn_add_edge(fn, 0, 2, 13);
344 fn_add_edge(fn, 1, 2, 10);
345 fn_add_edge(fn, 1, 3, 12);
346 fn_add_edge(fn, 2, 1, 4);
347 fn_add_edge(fn, 2, 4, 14);
348 fn_add_edge(fn, 3, 2, 9);
349 fn_add_edge(fn, 3, 5, 20);
350 fn_add_edge(fn, 4, 3, 7);
351 fn_add_edge(fn, 4, 5, 4);
352
353 printf(" κ·Έλν:\n");
354 printf(" 0 β 1 (16), 0 β 2 (13)\n");
355 printf(" 1 β 2 (10), 1 β 3 (12)\n");
356 printf(" 2 β 1 (4), 2 β 4 (14)\n");
357 printf(" 3 β 2 (9), 3 β 5 (20)\n");
358 printf(" 4 β 3 (7), 4 β 5 (4)\n");
359 printf(" μ΅λ μ λ (0β5): %d\n", edmonds_karp(fn, 0, 5));
360 fn_free(fn);
361
362 /* 2. μ΄λΆ λ§€μΉ */
363 printf("\n[2] μ΄λΆ 맀μΉ\n");
364 BipartiteGraph* bg = bg_create(4, 4);
365 /* μμ
μ(0-3)μ μμ
(0-3) λ§€μΉ */
366 bg_add_edge(bg, 0, 0);
367 bg_add_edge(bg, 0, 1);
368 bg_add_edge(bg, 1, 0);
369 bg_add_edge(bg, 1, 2);
370 bg_add_edge(bg, 2, 1);
371 bg_add_edge(bg, 2, 2);
372 bg_add_edge(bg, 3, 2);
373 bg_add_edge(bg, 3, 3);
374
375 printf(" μμ
μ-μμ
μ°κ²°:\n");
376 printf(" μμ
μ0: μμ
0, μμ
1\n");
377 printf(" μμ
μ1: μμ
0, μμ
2\n");
378 printf(" μμ
μ2: μμ
1, μμ
2\n");
379 printf(" μμ
μ3: μμ
2, μμ
3\n");
380 printf(" μ΅λ 맀μΉ: %d\n", bipartite_matching(bg));
381
382 printf(" λ§€μΉ κ²°κ³Ό:\n");
383 for (int i = 0; i < bg->left_n; i++) {
384 if (bg->match_left[i] != -1) {
385 printf(" μμ
μ%d β μμ
%d\n", i, bg->match_left[i]);
386 }
387 }
388 bg_free(bg);
389
390 /* 3. μ΅μ λ²ν
μ€ μ»€λ² */
391 printf("\n[3] μ΅μ λ²ν
μ€ μ»€λ² (μ΄λΆ κ·Έλν)\n");
392 printf(" Konig's theorem: μ΅λ λ§€μΉ = μ΅μ λ²ν
μ€ μ»€λ²\n");
393 printf(" μ μμ μ μ΅μ λ²ν
μ€ μ»€λ²: 4\n");
394
395 /* 4. Ford-Fulkerson */
396 printf("\n[4] Ford-Fulkerson (κ°λ¨ μμ )\n");
397 memset(capacity_ff, 0, sizeof(capacity_ff));
398 capacity_ff[0][1] = 10;
399 capacity_ff[0][2] = 10;
400 capacity_ff[1][2] = 2;
401 capacity_ff[1][3] = 4;
402 capacity_ff[1][4] = 8;
403 capacity_ff[2][4] = 9;
404 capacity_ff[3][5] = 10;
405 capacity_ff[4][3] = 6;
406 capacity_ff[4][5] = 10;
407
408 printf(" μ΅λ μ λ (0β5): %d\n", ford_fulkerson(0, 5, 6));
409
410 /* 5. μμ© */
411 printf("\n[5] λ€νΈμν¬ νλ‘μ° μμ©\n");
412 printf(" - μ΄λΆ 맀μΉ: μμ
ν λΉ, κ²°νΌ λ¬Έμ \n");
413 printf(" - μ΅μ μ»·: λ€νΈμν¬ λΆν \n");
414 printf(" - μ΅λ λ
립 μ§ν© (μ΄λΆ κ·Έλν)\n");
415 printf(" - νλ‘μ νΈ μ ν λ¬Έμ \n");
416 printf(" - μν νλ¦\n");
417
418 /* 6. 볡μ‘λ */
419 printf("\n[6] 볡μ‘λ\n");
420 printf(" | μκ³ λ¦¬μ¦ | μκ°λ³΅μ‘λ |\n");
421 printf(" |------------------|---------------|\n");
422 printf(" | Ford-Fulkerson | O(E Γ f) |\n");
423 printf(" | Edmonds-Karp | O(VEΒ²) |\n");
424 printf(" | Dinic | O(VΒ²E) |\n");
425 printf(" | μ΄λΆ λ§€μΉ (DFS) | O(VE) |\n");
426 printf(" | Hopcroft-Karp | O(EβV) |\n");
427 printf(" f: μ΅λ μ λ\n");
428
429 printf("\n============================================================\n");
430
431 return 0;
432}