(라이님 블로그 대회 알고리즘 따라잡기 25) 네트워크 유량(Network Flow)

네트워크 유량에 대해 공부해보았다. 개념 자체는 어렵지 않은데 음의 유량 다루는 부분이 조금 생소했다. 

 

아래 라이님 블로그에 아주 잘 기술되어 있으므로 정독하는 것을 추천!

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220804885235&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

네트워크 유량(Network Flow) (수정: 2019-08-14)

 

⭐ 플로우 그래프의 가장 큰 특징 : 간선의 용량!

⭐ 어떤 길을 한 번만 지날 수 있다 == 그 간선의 용량이 1이다.

⭐ 또한 단방향 그래프도 역방향 간선을 인접 리스트에 추가해주어야 한다!!!

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_V = 52;
const int INF = 1000000000;

// 정점 문자를 0~51 사이의 번호로 바꿔주는 함수
inline int CtoI(char c) {
    return (c <= 'Z') ? c - 'A' : c - 'a' + 26;
}

int N;
int capacity[MAX_V][MAX_V] = { 0 }; // 용량
int flow[MAX_V][MAX_V] = { 0 }; // 유량
vector<int> adj[MAX_V]; // 인접 리스트

void input() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        char u, v;
        int w;
        scanf(" %c %c %d", &u, &v, &w);
        int from = CtoI(u), to = CtoI(v);
        capacity[from][to] += w;
        capacity[to][from] += w; // 같은 간선이 여러 번 들어올 수 있으므로 +=
        adj[from].push_back(to);
        adj[to].push_back(from); // 역방향 간선도 추가
    }
}

int bfs(int source, int sink, int parent[]) {
    fill(parent, parent + MAX_V, -1);
    queue<pair<int, int>> Q;
    Q.push({ source, INF });

    while (!Q.empty()) {
        int curr = Q.front().first;
        int curr_flow = Q.front().second;
        Q.pop();

        for (int next : adj[curr]) {
            if (parent[next] == -1 && capacity[curr][next] > flow[curr][next]) { // 방문하지 않았고, 용량이 남아 있을 때
                parent[next] = curr;
                int new_flow = min(curr_flow, capacity[curr][next] - flow[curr][next]);
                if (next == sink)
                    return new_flow;
                Q.push({ next, new_flow });
            }
        }
    }
    return 0;
}

int maxFlow(int source, int sink) {
    int total_flow = 0;
    int parent[MAX_V];

    int new_flow;
    while ((new_flow = bfs(source, sink, parent))) {
        total_flow += new_flow;
        int curr = sink;
        while (curr != source) {
            int prev = parent[curr];
            flow[prev][curr] += new_flow;
            flow[curr][prev] -= new_flow;
            curr = prev;
        }
    }
    return total_flow;
}

int main() {
    input();
    int source = CtoI('A'), sink = CtoI('Z');
    printf("%d\n", maxFlow(source, sink));
    return 0;
}

 

 

만약 2차원 배열을 만들어 쓰기에 메모리가 부족하다면 아래와 같이 dual을 사용해보자.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_V = 52;
const int INF = 1000000000;

// 간선 구조체
struct Edge {
    int to, capacity, flow;
    Edge* dual; // 자신의 역방향 간선을 가리키는 포인터
    Edge(int to, int capacity) : to(to), capacity(capacity), flow(0), dual(nullptr) {}
    int spare() { return capacity - flow; }
    void addFlow(int newFlow) {
        flow += newFlow;
        dual->flow -= newFlow;
    }
};

// 정점 문자를 0~51 사이의 번호로 바꿔주는 함수
inline int CtoI(char c) {
    return (c <= 'Z') ? c - 'A' : c - 'a' + 26;
}

void addEdge(vector<Edge*> adj[], int u, int v, int capacity) {
    Edge* e1 = new Edge(v, capacity);
    Edge* e2 = new Edge(u, 0);
    e1->dual = e2;
    e2->dual = e1;
    adj[u].push_back(e1);
    adj[v].push_back(e2);
}

int bfs(vector<Edge*> adj[], int source, int sink, int parent[], Edge* path[]) {
    fill(parent, parent + MAX_V, -1);
    queue<int> Q;
    Q.push(source);
    while(!Q.empty() && parent[sink] == -1) {
        int curr = Q.front();
        Q.pop();
        for(Edge* e : adj[curr]) {
            int next = e->to;
            if(e->spare() > 0 && parent[next] == -1) {
                Q.push(next);
                parent[next] = curr;
                path[next] = e;
                if(next == sink) return e->spare();
            }
        }
    }
    return 0;
}

int maxFlow(vector<Edge*> adj[], int source, int sink) {
    int totalFlow = 0;
    int parent[MAX_V];
    Edge* path[MAX_V];
    
    int newFlow;
    while((newFlow = bfs(adj, source, sink, parent, path)) > 0) {
        totalFlow += newFlow;
        for(int curr = sink; curr != source; curr = parent[curr]) {
            path[curr]->addFlow(newFlow);
        }
    }
    return totalFlow;
}

int main() {
    int N;
    scanf("%d", &N);
    
    vector<Edge*> adj[MAX_V];
    for(int i = 0; i < N; ++i) {
        char u, v;
        int w;
        scanf(" %c %c %d", &u, &v, &w);
        addEdge(adj, CtoI(u), CtoI(v), w);
    }

    int source = CtoI('A'), sink = CtoI('Z');
    printf("%d\n", maxFlow(adj, source, sink));
    
    return 0;
}