네트워크 플로우 — 최대 유량 문제의 원리

원래: A →(10)→ B  (용량 10)
유량 6을 보낸 후:
  순방향: A →(4)→ B   (잔여 용량 = 10-6 = 4)
  역방향: B →(6)→ A   (되돌릴 수 있는 유량 = 6)

    S →(1)→ A →(1)→ T
    S →(1)→ B →(1)→ T
    A →(1)→ B

경로 1: S→A→B→T (유량 1)
이제 S→A는 꽉 참. 하지만 S→B→... 도 가야 함.
역방향 간선 B→A를 통해:
경로 2: S→B→A→T (유량 1, B→A는 역방향으로 A→B의 유량 취소)

결과: 총 유량 2 (S→A→T: 1, S→B→T: 1)

public class EdmondsKarp {
    static int[][] capacity;
    static int[][] flow;
    static int n;

    public static int maxFlow(int source, int sink) {
        int totalFlow = 0;

        while (true) {
            // BFS로 증가 경로 찾기
            int[] parent = bfs(source, sink);
            if (parent == null) break; // 증가 경로 없음

            // 경로를 따라 보낼 수 있는 최대 유량 계산
            int pathFlow = Integer.MAX_VALUE;
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                pathFlow = Math.min(pathFlow,
                    capacity[u][v] - flow[u][v]);
            }

            // 유량 갱신
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                flow[u][v] += pathFlow;
                flow[v][u] -= pathFlow; // 역방향
            }

            totalFlow += pathFlow;
        }
        return totalFlow;
    }

    private static int[] bfs(int source, int sink) {
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        parent[source] = source;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);

        while (!queue.isEmpty()) {
            int u = queue.poll();

            for (int v = 0; v < n; v++) {
                // 잔여 용량이 있고 아직 방문하지 않은 노드
                if (parent[v] == -1 && capacity[u][v] - flow[u][v] > 0) {
                    parent[v] = u;
                    if (v == sink) return parent;
                    queue.offer(v);
                }
            }
        }
        return null; // 싱크에 도달 불가
    }
}

    S →(3)→ A →(2)→ T
    S →(2)→ B →(3)→ T

최대 유량 = 5 (S→A→T: 2, S→B→T: 2, S→A→... 추가 1)
아니, 재계산:
  S→A: 3, A→T: 2 → 병목 2
  S→B: 2, B→T: 3 → 병목 2
  최대 유량 = 4?

정확한 계산은 간선 구조에 따라 다르지만,
핵심: 최소 컷 = 네트워크에서 가장 취약한 지점의 총 용량

// 최소 컷: 잔여 그래프에서 소스에서 BFS 도달 가능한 노드 집합
public static Set<Integer> minCut(int source) {
    Set<Integer> reachable = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(source);
    reachable.add(source);

    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v = 0; v < n; v++) {
            if (!reachable.contains(v) && capacity[u][v] - flow[u][v] > 0) {
                reachable.add(v);
                queue.offer(v);
            }
        }
    }
    return reachable;
    // 최소 컷 간선: reachable에서 !reachable로 가는 포화된 간선
}

왼쪽 그룹: 사람 {A, B, C}
오른쪽 그룹: 업무 {1, 2, 3}
간선: 수행 가능한 조합

네트워크 구성:
  S → A(1), S → B(1), S → C(1)     // 소스에서 왼쪽으로 (용량 1)
  A → 1(1), A → 2(1)               // 원래 간선 (용량 1)
  B → 2(1), B → 3(1)
  C → 1(1), C → 3(1)
  1 → T(1), 2 → T(1), 3 → T(1)    // 오른쪽에서 싱크로 (용량 1)

최대 유량 = 최대 매칭

// 간단한 이분 매칭 (DFS 기반)
static int[] match; // match[v] = v와 매칭된 왼쪽 노드 (-1이면 미매칭)

public static int maxMatching(List<List<Integer>> adj, int leftSize, int rightSize) {
    match = new int[rightSize];
    Arrays.fill(match, -1);
    int result = 0;

    for (int u = 0; u < leftSize; u++) {
        boolean[] visited = new boolean[rightSize];
        if (dfsMatch(adj, u, visited)) {
            result++;
        }
    }
    return result;
}

private static boolean dfsMatch(List<List<Integer>> adj, int u, boolean[] visited) {
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            visited[v] = true;
            // v가 미매칭이거나, v의 현재 매칭 상대를 다른 곳에 배정할 수 있으면
            if (match[v] == -1 || dfsMatch(adj, match[v], visited)) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

// Dinic의 핵심 구조
// 1. BFS로 레벨 그래프 구성 (각 노드의 거리 레벨)
// 2. DFS로 차단 유량 찾기 (레벨이 증가하는 방향으로만 탐색)
// 3. 1-2를 반복하여 더 이상 증가 경로가 없을 때까지

클라이언트 → 로드밸런서(1000rps) → 서버A(300rps)
                                 → 서버B(500rps)
                                 → 서버C(400rps) → DB(800rps)

최대 처리량 = min(1000, 300+500+400, 800) = 800rps
→ DB가 병목 (최소 컷)