1/*
2 * λ€νΈμν¬ νλ‘μ° (Network Flow)
3 * Ford-Fulkerson, Edmonds-Karp, Dinic, Bipartite Matching
4 *
5 * κ·Έλνμμ μ΅λ μ λμ ꡬνλ μκ³ λ¦¬μ¦μ
λλ€.
6 */
7
8#include <iostream>
9#include <vector>
10#include <queue>
11#include <algorithm>
12#include <climits>
13#include <cstring>
14
15using namespace std;
16
17const int INF = INT_MAX;
18
19// =============================================================================
20// 1. Ford-Fulkerson (DFS)
21// =============================================================================
22
23class FordFulkerson {
24private:
25 int n;
26 vector<vector<int>> capacity;
27 vector<vector<int>> adj;
28
29 int dfs(int u, int t, int pushed, vector<bool>& visited) {
30 if (u == t) return pushed;
31
32 visited[u] = true;
33
34 for (int v : adj[u]) {
35 if (!visited[v] && capacity[u][v] > 0) {
36 int flow = dfs(v, t, min(pushed, capacity[u][v]), visited);
37 if (flow > 0) {
38 capacity[u][v] -= flow;
39 capacity[v][u] += flow;
40 return flow;
41 }
42 }
43 }
44
45 return 0;
46 }
47
48public:
49 FordFulkerson(int n) : n(n), capacity(n, vector<int>(n, 0)), adj(n) {}
50
51 void addEdge(int u, int v, int cap) {
52 capacity[u][v] += cap;
53 adj[u].push_back(v);
54 adj[v].push_back(u);
55 }
56
57 int maxFlow(int s, int t) {
58 int flow = 0;
59
60 while (true) {
61 vector<bool> visited(n, false);
62 int pushed = dfs(s, t, INF, visited);
63 if (pushed == 0) break;
64 flow += pushed;
65 }
66
67 return flow;
68 }
69};
70
71// =============================================================================
72// 2. Edmonds-Karp (BFS)
73// =============================================================================
74
75class EdmondsKarp {
76private:
77 int n;
78 vector<vector<int>> capacity;
79 vector<vector<int>> adj;
80
81public:
82 EdmondsKarp(int n) : n(n), capacity(n, vector<int>(n, 0)), adj(n) {}
83
84 void addEdge(int u, int v, int cap) {
85 capacity[u][v] += cap;
86 adj[u].push_back(v);
87 adj[v].push_back(u);
88 }
89
90 int maxFlow(int s, int t) {
91 int flow = 0;
92
93 while (true) {
94 vector<int> parent(n, -1);
95 queue<int> q;
96 q.push(s);
97 parent[s] = s;
98
99 while (!q.empty() && parent[t] == -1) {
100 int u = q.front();
101 q.pop();
102
103 for (int v : adj[u]) {
104 if (parent[v] == -1 && capacity[u][v] > 0) {
105 parent[v] = u;
106 q.push(v);
107 }
108 }
109 }
110
111 if (parent[t] == -1) break;
112
113 // κ²½λ‘μ μ΅μ μ©λ
114 int pushed = INF;
115 for (int v = t; v != s; v = parent[v]) {
116 pushed = min(pushed, capacity[parent[v]][v]);
117 }
118
119 // μ©λ μ
λ°μ΄νΈ
120 for (int v = t; v != s; v = parent[v]) {
121 capacity[parent[v]][v] -= pushed;
122 capacity[v][parent[v]] += pushed;
123 }
124
125 flow += pushed;
126 }
127
128 return flow;
129 }
130};
131
132// =============================================================================
133// 3. Dinic's Algorithm
134// =============================================================================
135
136class Dinic {
137private:
138 struct Edge {
139 int to, cap, rev;
140 };
141
142 int n;
143 vector<vector<Edge>> graph;
144 vector<int> level, iter;
145
146 bool bfs(int s, int t) {
147 fill(level.begin(), level.end(), -1);
148 queue<int> q;
149 level[s] = 0;
150 q.push(s);
151
152 while (!q.empty()) {
153 int v = q.front();
154 q.pop();
155
156 for (auto& e : graph[v]) {
157 if (e.cap > 0 && level[e.to] < 0) {
158 level[e.to] = level[v] + 1;
159 q.push(e.to);
160 }
161 }
162 }
163
164 return level[t] >= 0;
165 }
166
167 int dfs(int v, int t, int f) {
168 if (v == t) return f;
169
170 for (int& i = iter[v]; i < (int)graph[v].size(); i++) {
171 Edge& e = graph[v][i];
172 if (e.cap > 0 && level[v] < level[e.to]) {
173 int d = dfs(e.to, t, min(f, e.cap));
174 if (d > 0) {
175 e.cap -= d;
176 graph[e.to][e.rev].cap += d;
177 return d;
178 }
179 }
180 }
181
182 return 0;
183 }
184
185public:
186 Dinic(int n) : n(n), graph(n), level(n), iter(n) {}
187
188 void addEdge(int from, int to, int cap) {
189 graph[from].push_back({to, cap, (int)graph[to].size()});
190 graph[to].push_back({from, 0, (int)graph[from].size() - 1});
191 }
192
193 int maxFlow(int s, int t) {
194 int flow = 0;
195
196 while (bfs(s, t)) {
197 fill(iter.begin(), iter.end(), 0);
198 int f;
199 while ((f = dfs(s, t, INF)) > 0) {
200 flow += f;
201 }
202 }
203
204 return flow;
205 }
206};
207
208// =============================================================================
209// 4. μ΄λΆ λ§€μΉ (Hungarian / Hopcroft-Karp)
210// =============================================================================
211
212class BipartiteMatching {
213private:
214 int n, m;
215 vector<vector<int>> adj;
216 vector<int> matchL, matchR;
217 vector<bool> visited;
218
219 bool dfs(int u) {
220 for (int v : adj[u]) {
221 if (visited[v]) continue;
222 visited[v] = true;
223
224 if (matchR[v] == -1 || dfs(matchR[v])) {
225 matchL[u] = v;
226 matchR[v] = u;
227 return true;
228 }
229 }
230 return false;
231 }
232
233public:
234 BipartiteMatching(int n, int m) : n(n), m(m), adj(n), matchL(n, -1), matchR(m, -1) {}
235
236 void addEdge(int u, int v) {
237 adj[u].push_back(v);
238 }
239
240 int maxMatching() {
241 int result = 0;
242
243 for (int u = 0; u < n; u++) {
244 visited.assign(m, false);
245 if (dfs(u)) result++;
246 }
247
248 return result;
249 }
250
251 vector<pair<int, int>> getMatching() {
252 vector<pair<int, int>> result;
253 for (int u = 0; u < n; u++) {
254 if (matchL[u] != -1) {
255 result.push_back({u, matchL[u]});
256 }
257 }
258 return result;
259 }
260};
261
262// =============================================================================
263// 5. μ΅μ λΉμ© μ΅λ μ λ (MCMF)
264// =============================================================================
265
266class MCMF {
267private:
268 struct Edge {
269 int to, cap, cost, rev;
270 };
271
272 int n;
273 vector<vector<Edge>> graph;
274
275public:
276 MCMF(int n) : n(n), graph(n) {}
277
278 void addEdge(int from, int to, int cap, int cost) {
279 graph[from].push_back({to, cap, cost, (int)graph[to].size()});
280 graph[to].push_back({from, 0, -cost, (int)graph[from].size() - 1});
281 }
282
283 pair<int, int> minCostMaxFlow(int s, int t) {
284 int totalFlow = 0, totalCost = 0;
285
286 while (true) {
287 vector<int> dist(n, INF);
288 vector<int> prevV(n, -1), prevE(n, -1);
289 vector<bool> inQueue(n, false);
290 queue<int> q;
291
292 dist[s] = 0;
293 q.push(s);
294 inQueue[s] = true;
295
296 while (!q.empty()) {
297 int v = q.front();
298 q.pop();
299 inQueue[v] = false;
300
301 for (int i = 0; i < (int)graph[v].size(); i++) {
302 Edge& e = graph[v][i];
303 if (e.cap > 0 && dist[v] + e.cost < dist[e.to]) {
304 dist[e.to] = dist[v] + e.cost;
305 prevV[e.to] = v;
306 prevE[e.to] = i;
307 if (!inQueue[e.to]) {
308 q.push(e.to);
309 inQueue[e.to] = true;
310 }
311 }
312 }
313 }
314
315 if (dist[t] == INF) break;
316
317 // κ²½λ‘μ μ΅μ μ©λ
318 int flow = INF;
319 for (int v = t; v != s; v = prevV[v]) {
320 flow = min(flow, graph[prevV[v]][prevE[v]].cap);
321 }
322
323 // μ©λ μ
λ°μ΄νΈ
324 for (int v = t; v != s; v = prevV[v]) {
325 Edge& e = graph[prevV[v]][prevE[v]];
326 e.cap -= flow;
327 graph[v][e.rev].cap += flow;
328 }
329
330 totalFlow += flow;
331 totalCost += flow * dist[t];
332 }
333
334 return {totalFlow, totalCost};
335 }
336};
337
338// =============================================================================
339// 6. μ΅μ μ»·
340// =============================================================================
341
342vector<pair<int, int>> minCut(int n, vector<vector<int>>& capacity, int s, int t) {
343 // Edmonds-Karp μ€ν ν μμ¬ κ·Έλνμμ sμμ λλ¬ κ°λ₯ν μ μ μ°ΎκΈ°
344 vector<vector<int>> residual = capacity;
345 vector<vector<int>> adj(n);
346
347 for (int i = 0; i < n; i++) {
348 for (int j = 0; j < n; j++) {
349 if (capacity[i][j] > 0) {
350 adj[i].push_back(j);
351 adj[j].push_back(i);
352 }
353 }
354 }
355
356 // Max flow
357 while (true) {
358 vector<int> parent(n, -1);
359 queue<int> q;
360 q.push(s);
361 parent[s] = s;
362
363 while (!q.empty() && parent[t] == -1) {
364 int u = q.front();
365 q.pop();
366
367 for (int v : adj[u]) {
368 if (parent[v] == -1 && residual[u][v] > 0) {
369 parent[v] = u;
370 q.push(v);
371 }
372 }
373 }
374
375 if (parent[t] == -1) break;
376
377 int pushed = INF;
378 for (int v = t; v != s; v = parent[v]) {
379 pushed = min(pushed, residual[parent[v]][v]);
380 }
381
382 for (int v = t; v != s; v = parent[v]) {
383 residual[parent[v]][v] -= pushed;
384 residual[v][parent[v]] += pushed;
385 }
386 }
387
388 // BFSλ‘ sμμ λλ¬ κ°λ₯ν μ μ
389 vector<bool> reachable(n, false);
390 queue<int> q;
391 q.push(s);
392 reachable[s] = true;
393
394 while (!q.empty()) {
395 int u = q.front();
396 q.pop();
397
398 for (int v : adj[u]) {
399 if (!reachable[v] && residual[u][v] > 0) {
400 reachable[v] = true;
401 q.push(v);
402 }
403 }
404 }
405
406 // μ΅μ μ»· κ°μ
407 vector<pair<int, int>> cut;
408 for (int u = 0; u < n; u++) {
409 if (reachable[u]) {
410 for (int v = 0; v < n; v++) {
411 if (!reachable[v] && capacity[u][v] > 0) {
412 cut.push_back({u, v});
413 }
414 }
415 }
416 }
417
418 return cut;
419}
420
421// =============================================================================
422// ν
μ€νΈ
423// =============================================================================
424
425int main() {
426 cout << "============================================================" << endl;
427 cout << "λ€νΈμν¬ νλ‘μ° μμ " << endl;
428 cout << "============================================================" << endl;
429
430 // 1. Ford-Fulkerson
431 cout << "\n[1] Ford-Fulkerson (DFS)" << endl;
432 FordFulkerson ff(6);
433 ff.addEdge(0, 1, 16);
434 ff.addEdge(0, 2, 13);
435 ff.addEdge(1, 2, 10);
436 ff.addEdge(1, 3, 12);
437 ff.addEdge(2, 1, 4);
438 ff.addEdge(2, 4, 14);
439 ff.addEdge(3, 2, 9);
440 ff.addEdge(3, 5, 20);
441 ff.addEdge(4, 3, 7);
442 ff.addEdge(4, 5, 4);
443 cout << " μ΅λ μ λ (0 β 5): " << ff.maxFlow(0, 5) << endl;
444
445 // 2. Edmonds-Karp
446 cout << "\n[2] Edmonds-Karp (BFS)" << endl;
447 EdmondsKarp ek(6);
448 ek.addEdge(0, 1, 16);
449 ek.addEdge(0, 2, 13);
450 ek.addEdge(1, 2, 10);
451 ek.addEdge(1, 3, 12);
452 ek.addEdge(2, 1, 4);
453 ek.addEdge(2, 4, 14);
454 ek.addEdge(3, 2, 9);
455 ek.addEdge(3, 5, 20);
456 ek.addEdge(4, 3, 7);
457 ek.addEdge(4, 5, 4);
458 cout << " μ΅λ μ λ (0 β 5): " << ek.maxFlow(0, 5) << endl;
459
460 // 3. Dinic
461 cout << "\n[3] Dinic's Algorithm" << endl;
462 Dinic dinic(6);
463 dinic.addEdge(0, 1, 16);
464 dinic.addEdge(0, 2, 13);
465 dinic.addEdge(1, 2, 10);
466 dinic.addEdge(1, 3, 12);
467 dinic.addEdge(2, 1, 4);
468 dinic.addEdge(2, 4, 14);
469 dinic.addEdge(3, 2, 9);
470 dinic.addEdge(3, 5, 20);
471 dinic.addEdge(4, 3, 7);
472 dinic.addEdge(4, 5, 4);
473 cout << " μ΅λ μ λ (0 β 5): " << dinic.maxFlow(0, 5) << endl;
474
475 // 4. μ΄λΆ 맀μΉ
476 cout << "\n[4] μ΄λΆ 맀μΉ" << endl;
477 BipartiteMatching bm(4, 4);
478 bm.addEdge(0, 0);
479 bm.addEdge(0, 1);
480 bm.addEdge(1, 0);
481 bm.addEdge(1, 2);
482 bm.addEdge(2, 1);
483 bm.addEdge(2, 2);
484 bm.addEdge(3, 2);
485 bm.addEdge(3, 3);
486 cout << " μ΅λ 맀μΉ: " << bm.maxMatching() << endl;
487 cout << " 맀μΉ: ";
488 for (auto [l, r] : bm.getMatching()) {
489 cout << "(" << l << "," << r << ") ";
490 }
491 cout << endl;
492
493 // 5. MCMF
494 cout << "\n[5] μ΅μ λΉμ© μ΅λ μ λ" << endl;
495 MCMF mcmf(4);
496 mcmf.addEdge(0, 1, 2, 1);
497 mcmf.addEdge(0, 2, 1, 2);
498 mcmf.addEdge(1, 2, 1, 1);
499 mcmf.addEdge(1, 3, 1, 3);
500 mcmf.addEdge(2, 3, 2, 1);
501 auto [flow, cost] = mcmf.minCostMaxFlow(0, 3);
502 cout << " μ΅λ μ λ: " << flow << ", μ΅μ λΉμ©: " << cost << endl;
503
504 // 6. 볡μ‘λ μμ½
505 cout << "\n[6] 볡μ‘λ μμ½" << endl;
506 cout << " | μκ³ λ¦¬μ¦ | μκ°λ³΅μ‘λ | νΉμ§ |" << endl;
507 cout << " |----------------|-----------------|-------------------|" << endl;
508 cout << " | Ford-Fulkerson | O(Ef) | DFS, 무ν루ν κ°λ₯|" << endl;
509 cout << " | Edmonds-Karp | O(VEΒ²) | BFS, μμ μ |" << endl;
510 cout << " | Dinic | O(VΒ²E) | λ 벨 κ·Έλν |" << endl;
511 cout << " | μ΄λΆ λ§€μΉ | O(VE) | νκ°λ¦¬μ |" << endl;
512 cout << " | MCMF | O(VEf) or O(VΒ³E)| SPFA/Bellman-Ford |" << endl;
513
514 cout << "\n============================================================" << endl;
515
516 return 0;
517}