https://www.acmicpc.net/problem/6086
문제조건
- 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다.
- 병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다.
- 어떤 것에도 연결돼 있지 않은 파이프는 물을 흐르게 하지 못하므로 제거된다.
- A에서 Z까지의 최대 유량을 구하시오.
접근방법
처음보는 종류의 문제였다. 그래프를 기반으로 하는문제인것은 알겠는데, 이것을 말로 구현하자고 하니 잘 안되었다. 검색을,,,, 해서 알아봤더니, 이런 문제에 쓰이는 알고리즘이 따로 있었다.
우선 각 노드간의 간선의 가중치를 capacity(수용량)으로 두고, m(흐른물의양)/n(가중치) 로 나타낸다.
이때, 출발점부터 도착점까지 막힘없이 1이상의 유량이 흐를수 있다면 그 경로를 증가경로 라고한다.
Ford-Fulkerson
알고리즘이라기보단 최대유량문제에 관하여 접근하는 방법이라고 생각하면된다.
DFS 또는 BFS로 구현할수 있는데, 그런 구체적인 방법에 대한것은 뒤에서 하도록하고 접근법을 살펴보자.
기본적인 접근법은 Greedy(탐욕)이다. Greedy하게 접근하지만 흘려보낸 유량을 취소하고, 다른 경로로 유량이 흐를때 더 많은 유량이라면 어떻게 해줘야할까? 반대 방향의 간선에 유량이 흐른다 = 기존 간선에 있던 유량을 취소하고 우회한다. 가 핵심아이디어이다.
- 양방향 간선을 설정해준다.
- 증가경로를 찾는다.(경로중 가장 적은 가중치를 흘려보낸다.)
- 증가경로가 없을때 까지 (2)를 반복한다.
위 접근방법에서 증가경로를 찾는것을 BFS로 구현한것이 바로 Edmonds-Karp 알고리즘이다!
소스코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
#define MAX 100
using namespace std;
int n, edge[MAX][MAX], flow[MAX][MAX];
int path[MAX];
int edmonds() {
int res = 0;
int end = 'Z' - 'A';
while (1) {
memset(path, -1, sizeof(path));
queue<int> q;
q.push(0);
path[0] = 0;
//BFS로 도착점까지 경로탐색
while (!q.empty() && path[end] == -1) {
int cur = q.front();
q.pop();
for (int i = 0; i < MAX; i++) {
if (edge[cur][i] - flow[cur][i] > 0 && path[i] == -1) {
q.push(i);
path[i] = cur;
}
}
}
if (path[end] == -1) break;
int tmp = INT_MAX;
// 흐를수 있는 양이 가장 작은 것을 기준으로 경로에 추가
for (int i = end; i != 0; i = path[i]) tmp = min(edge[path[i]][i] - flow[path[i]][i], tmp);
for (int i = end; i != 0; i = path[i]) {
flow[path[i]][i] += tmp;
flow[i][path[i]] -= tmp;
}
res += tmp;
}
return res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
char a, b;
int c;
cin >> a >> b >> c;
int n1 = a - 'A';
int n2 = b - 'A';
edge[n1][n2] += c;
edge[n2][n1] += c;
}
cout << edmonds();
}