17. 최대 유량

17.md

0.00MB

0. 복습
1. 네트워크 플로우(최대 유량, Max Flow)

물의 발생지를 소스. 변수명은 s 추천
모든 물이 빨려 들어가는 마지막 점을 싱크. 변수명은 t 추천
각각의 파이프에 현재유량/최대유량을 저장하는 배열이 있어야 한다.

포드-풀커슨 알고리즘을 사용한다.

이 알고리즘의 핵심은 바로 유량의 대칭성을 만들어준다는 것이다.

어떤 경로로 유량을 흘렸으면 이 간선에 반대되는 간선을 만들고, 흘리는 유량 * -1 만큼 한 값을 넣어준다.

dfs로 했을 때 시간복잡도는 O(EF). 단, E는 간선, F는 최대 유량

bfs로 했을 때 시간복잡도는 O(min(EF, V(E^2))). BFS로 구현한다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N;
int c[200][200]; // c[a][b] : a->b의 간선의 용량
int f[200][200]; // f[a][b] : a->b의 간선의 유량
vector<int> G[200];

int MaxFlow(int src, int snk) { // src에서 snk로 가는 최대 유량을 리턴한다.
    int ret = 0;
    while(1){
        queue<int> q; q.push(src);
        vector<int> p(200, -1); p[src]=src;// parents
        while(!q.empty() && p[snk] == -1){//BFS로 역추적 배열을 채운다.
            int n = q.front(); q.pop();
            for(int i=0; i<G[n].size(); ++i){
                int next = G[n][i];
                if(c[n][next] - f[n][next] >0 && p[next] == -1){
                    q.push(next);
                    p[next] = n;
                }
            }
        }
        if(p[snk]==-1) break;
        int flow = 1234567890;//INF
        for(int i=snk; i!=src; i=p[i]){
            flow = min(flow, c[p[i]][i] - f[p[i]][i]);
        }
        for(int i=snk; i!=src; i=p[i]){
            f[p[i]][i] += flow;
            f[i][p[i]] -= flow;
        }
        ret += flow;
    }
    return ret;
}

int main(){
    cin >> N;
    for(int i=0; i<N; ++i){
        char a, b;
        int x;
        cin >> a >> b >> x;
        G[a].push_back(b);
        G[b].push_back(a); // 그래프는 양방향으로
        c[a][b] += x;//단방향이면 이거만
        c[b][a] += x;//양방향이면 이거도
    }
    cout << MaxFlow((int)'A', (int)'Z') << '\n';
}

최대 유량을 활용하는 문제는 다양하다.

최소 컷 문제, 즉 그래프에서 간선의 가중치의 합을 최소화하면서 제거하는 문제.

최대 유량 문제로 바꿔서 풀 수 있다. 최대 유량 최소 컷 정리 참고.

최소 정점 덮개 문제도 같다.
정점을 선택하면 그 정점과 인접하는 모든 정점을 색칠한다.
모든 정점을 색칠하기 위해 선택해야 하는 최소한의 정점을 구하는 문제.

최대유량의 수로 답이 구해진다. 단, 이분그래프일때만 답이 나온다.

최대 독립 집합 문제도 같다.
최대한 많은 정점을 선택해야 한다. 단, 선택하는 정점들은 이웃하면 안된다.

이 문제는 N-최대유량으로 답이 구해진다. 단, 이분그래프일때만.

참고로 최소 정점 덮개 문제의 여집합이 곧 최대 독립 집합이다.

참고 : 6086, 17412, 2316, 2188, 1574, 16726, 11495, 1671, 1017