네트워크 유량

정의

1. 컷 : 그래프를 2개의 서로 다른 집합으로 나누는 것.

가중치가 없는 그래프 - 자른 간선의 개수가 cut의 비용.

가중치가 있는 그래프 - 가중치의 합이 cut의 비용.

 

2. 유량 

각 간선은 용량을 가지고 있고, 해당 간선으로 얼마나 많은 유량이 흐를 수 있는지이다.

용량 - 각 간선에 할당된 유량은 그 간선의 용량을 초과할 수 없다.

유량 보존 - 출발점과 도착점을 제외한 모든 정점에서는 들어오는 유량과 나가는 유량이 같다.

 

3. 최대 유량 최소 컷 정리 (MFMC)

 

최대 유량 - 네트워크 출발점에서 도착점으로 보낼 수 있는 가장 큰 유량

최소 컷 - 간선을 가장 적게 자를 때 혹은 간선의 가중치 합이 가장 적을 때 용량의 최소합

 

핵심 - 정점 A와 B를 분리시키는 최소 컷의 비용은 A에서 B로 흐를 수 있는 최대 유량과 같다.

 

최대 유량은 보틀넥을 떠올리게 한다. 

예컨대 네트워크 망에서 보틀넥 구간이 있다면 다른 구간의 대역폭을 아무리 늘려도 보틀넥 구간으로 대역폭 상한이 정해진다.

 

구현 

Ford-Fulkerson 알고리즘

 

1. 출발점에서 도착점으로 아무 유량이 흐르지 않는 상태에서 시작.
2. 잔여 용량이 남아있는 경로(증가 경로)를 찾아서 그 경로를 따라 유량을 보냄.
3. 경로를 찾을 때마다 유량을 갱신하고 잔여 그래프 갱신
4. 더 이상 경로를 찾을 수 없을 때 최대 유량이 됨

https://www.acmicpc.net/problem/14286

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<stack>
#include<cmath>
#define INF 1e9
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
 
vector<vector<int>> v;
 
int capacity[501][501]; // 용량
int flow[501][501];
int total_flow;
int parent[501]; // 최대 유량용 부모
int s, t;
 
void maxflow() {
    while(true) {
        memset(parent, -1, sizeof(parent));
        
        queue<int> q;
        q.push(s);
        
        // t에 도달하는 경로가 있으면 종료
        while(!q.empty() && parent[t] == -1) {
            int cur = q.front(); q.pop();
            
            for(auto next : v[cur]) {
                if(capacity[cur][next] - flow[cur][next] > 0 && parent[next] == -1) {
                    q.push(next);
                    parent[next] = cur;
                }
            }
        }
        
        // 더 이상 t에 도달하는 경로를 찾지 못하면 종료
        if(parent[t] == -1) {
            break;
        }
        
        int amount = INF;
        
        // t에서 s로 가면서 유량의 최솟값을 구함 (s->t는 bfs로 여러 갈래로 흩어지므로 parent를 이용해 거꾸로 타고가며 최종 경로를 구한다)
        for(int p=t; p!=s; p=parent[p]) {
            amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
        }
        
        // 유량을 업데이트한다.
        for(int p=t; p!=s; p=parent[p]) {
            flow[parent[p]][p] += amount;   // s->t로 흐르기 때문에 유량을 더해준다.
            flow[p][parent[p]] -= amount; // a->b로 x가 흐른다면 b->a로 -x가 흐르는 것과 같다.
        }
        
        total_flow += amount; // 최대 유량 업데이트
    }
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    v = vector<vector<int>>(n+1);
    memset(flow, 0, sizeof(flow));
    
    for(int i=0; i<m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        v[x].push_back(y);
        v[y].push_back(x);
        
        capacity[x][y] = capacity[y][x] = z;
    }
    
    cin >> s >> t;
    maxflow();
    
    cout << total_flow;
    
    return 0;
}
 

증명

 

살펴볼 예정.

참고

https://flappybird.tistory.com/57

https://gazelle-and-cs.tistory.com/62