[C++] 네트워크 유량(Network Flow)

네트워크 유량(Network Flow)

그래프 개념 중 하나로 네트워크 유량을 이해하기 위해선 먼저 새로운 용어와 유량 그래프의 특징부터 알아야 한다.

• 유량 그래프는 보통 방향 그래프인 경우가 많다.
• 그래프의 간선 거리, 시간이나 가중치 대신 용량(Capacity)이라 한다.
• 두 정점 u, v를 있는 간선 (u, v)가 있을 때, u에서 v로 간선의 용량 이하만큼의 유량(flow)을 흘려보낼 수 있다.
• 그래프 내 서로 다른 소스(S, Source) 정점과 싱크(T, Sink) 정점이 있는데, 소스 정점은 유량을 발생시킨다.
  • 소스 정점 외 정점들은 자신이 받은 유량만큼만 다시 흘려보낸다.
  • 각 간선에 흐르는 유량은 그 간선의 용량을 넘을 수 없다.
  • 간선 (u, v)로 유량이 흐르고 있다면 역방향인 간선(v, u)은 음의 유량이 그만큼 흐르고 있다.

 

네트워크 유량은 그래프 내 소스 정점에서 유량을 발생시켜 간선을 통해 싱크 정점에 도달시키는 것이 목표이다.

 

최대 유량 알고리즘

S에서 T로 유량 1을 보내면, 유량 1을 보낼 수 있을 정도로 용량이 충분한 간선을 찾아 T까지 보낸다. 이때, 유량을 흘려보내는 것을 도중에 멈춰서는 안 된다. 반드시 T까지 도달해야 유효하다.

 

유량 1

 

유량 1(S-A)을 보낸 후 다시 한번 유량 1(S-B)과 유량 4(S-C)를 보낸 후 결과이다.

 

유량 1 + 유량1 + 유량4

 

지금까지 S에서 T로 보낸 유량의 합은 6인데, 여기서 더 많은 유량을 T로 보낼 수 있을까? 불가능하다. 왜냐하면 경로에 속한 간선 (D, T)엔 더 이상 용량이 남아있지 않다.

 

더 많은 유량을 보내는 방법은 없을까?

 

유량 7

 

처음 경로가 아닌 최대 유량 알고리즘을 따라 경로를 찾으면 더 많은 유량을 보낼 수 있게 된다.

 

1. 포드 풀커슨 알고리즘(Ford-Fulkerson algorithm)

DFS로 구현한 알고리즘으로 기초가 되는 알고리즘이다.

 

1) 기본 원리

• S에서 T로 가는 증가 경로 중 아무거나 하나를 찾는다.
• 증가 경로 중 차단 간선을 찾는다. 이 간선은 경로상에서 F(c(u, v) - f(u, v)) 값이 최소인 간선이다.
• 경로 내 모든 간선에 F 유량을 추가한다. 즉, S에서 T로 이 경로를 따라서 F만큼의 유량을 새로 흘려보낸 것이다.
• 이때, 음의 유량도 만족해야 하기 때문에 역방향도 이동 가능하다.
• 위 과정을 더 이상 증가 경로가 없을 때까지 반복한다.

 

유량 3(S-A) + 유량 2(S-B) + 유량4(S-C)

역방향 경로 수행 - 유량 3(S-A) + 유량 2(S-B) + 유량4(S-C) + 유량 1(S-C)

 

2) 문제

 

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

6086번: 최대 유량

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int getID(char c)
{
	if (c <= 'Z')
		return c - 'A';
	return c - 'a' + 26;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N; // 간선 수
	int c[52][52]; // c[i][j]: i에서 j로 가는 간선의 용량
	int f[52][52]; // f[i][j]: i에서 j로 현재 흐르는 유량
	vector<int> map[52]; // 인접 리스트

	cin >> N;
	for (int i = 0; i < N; i++) {
		char u, v;
		int w;
		cin >> u >> v >> w;

		int U = getID(u), V = getID(v);
		map[U].push_back(V);
		map[V].push_back(U); // 역방향 간선
		c[U][V] += w;
		c[V][U] += w;
	}

	int maximumFlow = 0, s = 0, t = 25;
	while (true) {
		int visit[52]{};
		fill(visit, visit + 52, -1);

		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int front = q.front();
			q.pop();

			for (int i = 0; i < map[front].size(); i++) {
				int next = map[front][i];
				if (c[front][next] - f[front][next] > 0 && visit[next] == -1) {
					q.push(next);
					visit[next] = front;

					if (next == t)
						break;
				}
			}
		}

		// 증가 경로가 없다면 탈출
		if (visit[t] == -1)
			break;

		int flow = 1e9;

		// 차단 간선 찾기
		for (int i = t; i != s; i = visit[i])
			flow = min(flow, c[visit[i]][i] - f[visit[i]][i]);

		// 차단 간선 용량만큼 유량 흘리기
		for (int i = t; i != s; i = visit[i]) {
			f[visit[i]][i] += flow;
			f[i][visit[i]] -= flow;
		}

		maximumFlow += flow;
	}

	cout << maximumFlow;
}

 

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

17412번: 도시 왕복하기 1

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int c[401][401];
int f[401][401];
vector<int> map[401];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, P;
	cin >> N >> P;
	while (P--) {
		int u, v;
		cin >> u >> v;

		map[u].push_back(v);
		map[v].push_back(u);
		c[u][v] = 1;
		c[v][u] = 0;
	}

	int maximumFlow = 0, s = 1, t = 2;
	while (true) {
		int visit[401]{};
		fill(visit, visit + 401, -1);

		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int front = q.front();
			q.pop();

			for (int i = 0; i < map[front].size(); i++) {
				int next = map[front][i];
				if (c[front][next] - f[front][next] > 0 && visit[next] == -1) {
					q.push(next);
					visit[next] = front;

					if (next == t)
						break;
				}
			}
		}

		// 증가 경로가 없다면 탈출
		if (visit[t] == -1)
			break;

		int flow = 1e9;

		// 차단 간선 찾기
		for (int i = t; i != s; i = visit[i])
			flow = min(flow, c[visit[i]][i] - f[visit[i]][i]);

		// 차단 간선 용량만큼 유량 흘리기
		for (int i = t; i != s; i = visit[i]) {
			f[visit[i]][i] += flow;
			f[i][visit[i]] -= flow;
		}

		maximumFlow += flow;
	}

	cout << maximumFlow;
}

 

2. 에드몬드 카프 알고리즘(Edmonds-Karp algorithm)

BFS로 구현한 알고리즘으로 포드 풀커슨 알고리즘과 기본 동작은 동일하지만 시간 복잡도가 훨씬 효율적이다.

 

3. 디닉 알고리즘(Dinic's algorithm)

대부분 유량 문제는 앞선 두 알고리즘으로 풀리지만 간혹 더 빠른 시간 복잡도를 요구하는 문제가 있다. 그러한 문제는 디닉 알고리즘을 사용해야 한다.

 

1) 기본 원리

• 레벨 그래프(level graph)를 만든다. 이때 싱크에 도달할 수 없다면 종료한다.
  • 모든 정점에 대해 소스에서부터 최단거리를 레벨 값으로 매겨놓은 그래프이다.
  • 여유 용량이 없는 간선은 사용할 수 없다.
  • 레벨 그래프에서 존재하지 않는 간선은 점선으로 표시한다.
• 레벨 그래프에서 차단 유량(blocking flow)을 찾아 총유량에 더하고 다시 레벨 그래프를 만든다.
  • 레벨 그래프에서는 항상 인접하면서 자신보다 레벨이 1 큰 정점으로 이동이 가능하다.
  • 더 이상 소스에서 싱크로 흘릴 수 있는 유량이 없게 만드는 유량 상태를 말한다.

 

초기 그래프 1

레벨 그래프 1 - 차단 유량 14

초기 그래프 2 - 유량 14

레벨 그래프 2 - 차단 용량 5

초기 그래프 3 - 유량 19

레벨 그래프 3 - 차단 용량 없음

 

2) 문제

 

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

13161번: 분단의 슬픔

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 500;
const int MAX_V = MAX_N + 2;
const int S = MAX_V - 2;
const int E = MAX_V - 1;
const int INF = 1000000000;

vector<int> adj[MAX_V];
int c[MAX_V][MAX_V], f[MAX_V][MAX_V];
int level[MAX_V], work[MAX_V];

// 레벨 그래프(level graph) 만들기
bool LevelGraph()
{
    fill(level, level + MAX_V, -1);
    level[S] = 0;

    queue<int> Q;
    Q.push(S);
    while (!Q.empty()) {
        int curr = Q.front();
        Q.pop();
        for (int next : adj[curr]) {
            // 레벨값이 설정되지 않았고 간선에 여유 용량이 있을 때 이동
            if (level[next] == -1 && c[curr][next] - f[curr][next] > 0) {
                level[next] = level[curr] + 1; // next의 레벨은 curr의 레벨 + 1
                Q.push(next);
            }
        }
    }

    return level[E] != -1; // 싱크에 도달 가능하면 true
}

// 차단 유량(blocking flow) 구하기: curr에서 dest까지 최대 flow 유량을 보낼 수 있는지
int BlockingFlow(int curr, int dest, int flow)
{
    if (curr == dest)
        return flow;

    // 이미 쓸모없다고 판단한 간선은 다시 볼 필요가 없으므로 work 배열로 간선 인덱스를 저장
    for (int& i = work[curr]; i < adj[curr].size(); i++) {
        int next = adj[curr][i];
        // next 레벨이 curr 레벨 + 1이고 간선에 여유 용량이 있을 때 이동
        if (level[next] == level[curr] + 1 && c[curr][next] - f[curr][next] > 0) {
            // df: 경로상의 간선들 중 가장 작은 여유 용량
            int df = BlockingFlow(next, dest, min(c[curr][next] - f[curr][next], flow));            
            if (df > 0) { // 증가 경로가 있다면 df 유량을 흘리고 종료
                f[curr][next] += df;
                f[next][curr] -= df;
                return df;
            }
        }
    }

    return 0; // 증가 경로를 찾지 못함
}

int Dinic()
{
    int total = 0;

    while (LevelGraph()) { // 싱크에 도달할 수 없다면 종료      
        fill(work, work + MAX_V, 0);
        while (1) {
            int flow = BlockingFlow(S, E, INF);
            if (flow == 0)
                break; // 더 이상 차단 유량이 없다면 종료
            total += flow;
        }
    }

    return total;
}

int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int team;
        cin >> team;
        if (team == 1) {
            c[S][i] = INF;
            adj[S].push_back(i);
            adj[i].push_back(S);
        }
        else if (team == 2) {
            c[i][E] = INF;
            adj[i].push_back(E);
            adj[E].push_back(i);
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> c[i][j];
            if (i != j)
                adj[i].push_back(j);
        }
    }

    cout << Dinic() << '\n';

    // 각 진영에 속한 사람을 판단하기 위해 소스에서의 도달 가능성 판별
    bool visited[MAX_V]{ false };
    visited[S] = true;
    queue<int> Q;
    Q.push(S);
    while (!Q.empty()) {
        int curr = Q.front();
        Q.pop();
        for (int next : adj[curr]) {
            // 여유 용량이 남아있는 간선만을 이용
            if (!visited[next] && c[curr][next] - f[curr][next] > 0) {
                visited[next] = true;
                Q.push(next);
            }
        }
    }

    // A진영에 속한 사람들: 소스에서 도달 가능
    for (int i = 0; i < N; i++)
        if (visited[i])
            cout << i + 1 << ' ';
    cout << '\n';
    // B진영에 속한 사람들: 소스에서 도달 불가능
    for (int i = 0; i < N; i++)
        if (!visited[i])
            cout << i + 1 << ' ';
    cout << '\n';
}

 

4. 호프크로프트 카프 알고리즘

1) 문제

 

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

3736번: System Engineer

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 10000;
const int INF = 1000000000;

int N;
// A[i], B[i]: 그룹의 i번 정점과 매칭된 상대편 그룹 정점 번호
// dist[i]: (A그룹의) i번 정점의 레벨(?)
// used: (A그룹의) 이 정점이 매칭에 속해 있는가?
int A[MAX], B[MAX], dist[MAX];
bool used[MAX];
vector<int> adj[MAX];

void bfs()
{
    queue<int> Q;
    for (int i = 0; i < N; i++) {
        // 매칭에 안 속한 A그룹의 정점만 레벨 0인 채로 시작
        if (!used[i]) {
            dist[i] = 0;
            Q.push(i);
        }
        else
            dist[i] = INF;
    }

    // A그룹 정점에 0, 1, 2, 3, ... 의 레벨을 매김
    while (!Q.empty()) {
        int a = Q.front();
        Q.pop();
        for (int b : adj[a]) {
            if (B[b] != -1 && dist[B[b]] == INF) {
                dist[B[b]] = dist[a] + 1;
                Q.push(B[b]);
            }
        }
    }
}

// 이분 매칭 알고리즘
bool dfs(int a)
{
    for (int b : adj[a]) {
        // 이분 매칭과 차이점: dist 배열에 대한 조건이 추가로 붙음
        if (B[b] == -1 || dist[B[b]] == dist[a] + 1 && dfs(B[b])) {
            used[a] = true;
            A[a] = b;
            B[b] = a;
            return true;
        }
    }
    return false;
}

int main()
{
    while (cin >> N) {
        // Init
        fill(A, A + MAX, -1);
        fill(B, B + MAX, -1);
        fill(used, used + MAX, false);
        for (int i = 0; i < N; i++)
            adj[i].clear();

        // Input
        for (int i = 0; i < N; i++) {
            int job, server, M;
            scanf("%d: (%d)", &job, &M);
            for (int j = 0; j < M; j++) {
                cin >> server;
                adj[job].push_back(server - N);
            }
        }

        // 호프크로프트 카프 알고리즘
        int answer = 0;
        while (1) {
            // 각 정점에 레벨을 매기고 시작
            bfs();

            // 이분 매칭 알고리즘을 이용해 증가 경로 찾기
            int flow = 0;
            for (int i = 0; i < N; i++)
                if (!used[i] && dfs(i))
                    flow++;
            answer += flow;

            // 더 이상 증가 경로를 못 찾으면 알고리즘 종료
            if (flow == 0)
                break;
        }

        cout << answer << '\n';
    }
}

 

최소 비용 최대 유량(MCMF, Min-Cost Max-Flow)

최대 유량을 발생시키는데, 최소 비용을 통해 흘려야 한다.

• 그래프의 간선에 또 다른 가중치인 비용(Cost)이 존재한다.
• 비용은 간선마다 다르며 비용이 d이고 f만큼의 유량이 흐르고 있을 때, 소비되는 비용은 d*f이다.
• 경로 비용은 지나간 모든 간선 비용의 합이다.

 

원리는 최대 유량 알고리즘과 비슷하다. 경로를 찾아 유량을 흘리고 이 과정을 더 이상 경로가 없을 때까지 반복하는 것인데, 이때 찾는 경로가 최단 경로이다. 즉, 간선 비용을 기준으로 최단 경로를 찾으면 된다.

 

그런데, 유량 그래프에서는 역방향 간선도 존재하기 때문에 음의 가중치에서도 잘 동작해야 한다. 역방향 간선으로 유량을 흘리면 그만큼 유량과 비용이 모두 줄어든다.

 

1. SPFA(Shortest Path Faster Algorithm)

SPFA

 

1) 문제

 

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

11408번: 열혈강호 5

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> v[802];
int s = 0, t = 801;
int ca[802][802], fl[802][802], cost[802][802];

int main()
{
	int n, m;
	cin >> n >> m;

	// Source와 사람 양방향 연결
	for (int i = 1; i <= n; i++) {
		v[s].push_back(i);
		v[i].push_back(s);
		ca[s][i] = 1; // 용량은 순방향만 추가
	}

	// 일과 Sink 양방향 연결
	for (int i = 1; i <= m; i++) {
		v[t].push_back(i + 400);
		v[i + 400].push_back(t);
		ca[i + 400][t] = 1; // 용량은 순방향만 추가
	}

	// 사람과 일 연결
	for (int i = 1; i <= n; i++) {
		int cnt;
		cin >> cnt;

		for (int j = 0; j < cnt; j++) {
			int num, money;
			cin >> num >> money;

			// 사람과 일 양방향 연결
			v[i].push_back(num + 400);
			v[num + 400].push_back(i);

			// 용량은 순방향만 추가
			ca[i][num + 400] = 1;

			// 비용은 양방향
			cost[i][num + 400] = money;
			cost[num + 400][i] = -money;
		}
	}

	// MCMF
	int ans = 0, result = 0;
	while (1) {
		int pre[802]; // 이전 노드 저장
		int dist[802]; // s로부터 최단거리
		fill(dist, dist + 802, 2e9);
		fill(pre, pre + 802, -1);

		queue<int> q;
		bool visit[802]{};

		q.push(s);
		visit[s] = true;
		dist[s] = 0;

		while (!q.empty()) {
			int node = q.front(); q.pop();
			visit[node] = false;

			for (auto next : v[node]) {
				if (dist[next] > dist[node] + cost[node][next] && ca[node][next] > fl[node][next]) {
					dist[next] = dist[node] + cost[node][next];
					pre[next] = node;
					if (!visit[next]) {
						visit[next] = true;
						q.push(next);
					}
				}
			}
		}

		// 최단 경로가 더이상 없음
		if (pre[t] == -1)
			break;

		int flow = 2e9;
		for (int i = t; i != s; i = pre[i]) {
			flow = min(flow, ca[pre[i]][i] - fl[pre[i]][i]);
		}
		for (int i = t; i != s; i = pre[i]) {
			result += cost[pre[i]][i];
			fl[pre[i]][i] += flow;
			fl[i][pre[i]] -= flow;
		}
		ans += flow;
	}

	cout << ans << "\n" << result << "\n";
}