백준 BOJ 최대 유량 알고리즘 문제 다시 풀어보기 (Network Flow)

과거에 풀어놨던 최대 유량 알고리즘 문제들의 풀이들이 더럽기도 하고 설명도 깔끔하지 못해서 다시 한 번 풀면서 풀이 코드만 비교적 간단하게 정리해보려고 합니다.

푸는 순서의 기준은 최대 유량 알고리즘에 속해 있는 문제들 중 푼 사람 수가 많은 문제부터 내림차순입니다.

각 문제의 풀이 코드는 문제 설명 바로 아래 접은 글에 정리되어 있습니다.

 

참고로 문제 풀이에 대한 간략한 설명은 있으나 최대 유량 알고리즘 자체에 대한 설명이나 코드에 대한 구체적인 작동 방식의 설명은 없습니다.

이 블로그 내 검색(지금 보시는 페이지 상단에 검색 창이 있습니다.)을 통해 문제 번호만 숫자로 입력하면 알고리즘과 코드에 대한 구체적인 설명이 정리되어 있습니다.

 

 

백준 BOJ 6086번 : 최대 유량

문제 난이도 : Platinum IV

알고리즘 분류 : 최대 유량

 

두 파이프의 알파벳과 그 사이의 유량 제한이 주어질 때, A 파이프에서 Z 파이프까지 흐를 수 있는 최대 유량을 구하는 문제입니다.

 

↓ 풀이 코드

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, cap, flo;

int f(char c) {
    if(c >= 'A' && c <= 'Z') return c - 'A' + 1;
    else if(c >= 'a' && c <= 'z') return c - 'a' + 27;
}

int mf(int sour, int dest) {
    int sum = 0;

    while(true) {
        vector<int> p(60, -1);

        queue<int> q;
        q.push(sour);

        while(!q.empty() && p[dest] == -1) {
            int x = q.front();
            q.pop();

            for(int i=0; i<adj[x].size(); i++) {
                int y = adj[x][i];

                if(cap[x][y] - flo[x][y] <= 0 || p[y] != -1) continue;

                p[y] = x;
                q.push(y);

                if(y == dest) break;
            }
        }
        if(p[dest] == -1) break;

        int val = INT_MAX;

        for(int i=dest; i!=sour; i=p[i])
            val = min(val, cap[p[i]][i] - flo[p[i]][i]);

        for(int i=dest; i!=sour; i=p[i]) {
            flo[p[i]][i] += val;
            flo[i][p[i]] -= val;
        }

        sum += val;
    }

    return sum;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    adj.resize(60);
    cap.resize(60, vector<int>(60));

    while(N--) {
        char a, b; int c; cin >> a >> b >> c;

        adj[f(a)].push_back(f(b));
        adj[f(b)].push_back(f(a));

        cap[f(a)][f(b)] += c;
        cap[f(b)][f(a)] += c;
    }

    flo.resize(60, vector<int>(60));

    cout << mf(f('A'), f('Z')) << "\n";
}

 

 

백준 BOJ 11377번 : 열혈강호3

문제 난이도 : Platinum III

알고리즘 분류 : 최대 유량

 

N명의 직원이 있고 각각이 할 수 있는 일의 번호가 주어지며, N명 중 K명은 2개의 일을 할 수 있을 때 모두 합쳐 최대 몇 개의 서로 다른 일을 하도록 배치할 수 있는지를 구하는 문제이다.

 

그래프를 적절히 세팅하여 최대 유량 알고리즘으로 풀이할 수 있는 문제이다.

N명의 직원이 각각 할 수 있는 일을 연결하고 그 유량을 1로 설정한다.

그리고 K의 유량을 가지고 있는 노드를 N명의 직원에 각각 유량 제한을 1로 설정한다.

이 상태에서 최대 유량을 구해보면 dest 노드로 도달하는 최대 유량이 최대 할 수 있는 일의 개수, 즉 답이 된다.

 

N과 M의 범위를 활용하여 1000 단위로 끊어서 노드를 넘버링하였다.

대신 이럴 경우 메모리를 낭비하는 경우가 많아 코드 작동 시간이 조금 더 오래 걸린다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, cap, flo;

int mf(int sour, int dest) {
    int sum = 0;

    while(true) {
        vector<int> p(2005, -1);

        queue<int> q;
        q.push(sour);

        while(!q.empty() && p[dest] == -1) {
            int x = q.front();
            q.pop();

            for(int i=0; i<adj[x].size(); i++) {
                int y = adj[x][i];

                if(cap[x][y] - flo[x][y] <= 0 || p[y] != -1) continue;

                p[y] = x;
                q.push(y);

                if(y == dest) break;
            }
        }
        if(p[dest] == -1) break;

        int val = INT_MAX;

        for(int i=dest; i!=sour; i=p[i])
            val = min(val, cap[p[i]][i] - flo[p[i]][i]);

        for(int i=dest; i!=sour; i=p[i]) {
            flo[p[i]][i] += val;
            flo[i][p[i]] -= val;
        }

        sum += val;
    }

    return sum;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M, K; cin >> N >> M >> K;

    adj.resize(2005);
    cap.resize(2005, vector<int>(2005));
    flo.resize(2005, vector<int>(2005));

    int sour = 2001, dest = 2002, k = 2003;

    adj[sour].push_back(k);
    adj[k].push_back(sour);
    cap[sour][k] = K;

    for(int i=1; i<=N; i++) {
        adj[sour].push_back(i);
        adj[i].push_back(sour);
        cap[sour][i] = 1;

        adj[k].push_back(i);
        adj[i].push_back(k);
        cap[k][i] = 1;

        int L; cin >> L;

        while(L--) {
            int x; cin >> x;

            adj[i].push_back(1000+x);
            adj[1000+x].push_back(i);
            cap[i][1000+x] = 1;
        }
    }

    for(int i=1001; i<=1000+M; i++) {
        adj[i].push_back(dest);
        adj[dest].push_back(i);
        cap[i][dest] = 1;
    }

    cout << mf(sour, dest) << "\n";
}