최대 흐름 - 개선된 Push-relabel 방법¶

더 나은 실행 시간을 얻기 위해 푸시-재레이블 방법을 수정하겠습니다.

설명¶

수정 사항은 매우 간단합니다. 이전 글에서는 초과량이 있는 정점을 특별한 규칙 없이 선택했습니다. 그런데 항상 가장 높은 높이를 가진 정점들을 선택하여 이 정점들에 푸시 연산과 재레이블 연산을 적용하면 복잡도가 더 좋아진다는 사실이 밝혀졌습니다. 또한 높이가 가장 큰 정점을 선택하는 데에는 사실 어떤 자료 구조도 필요하지 않습니다. 높이가 가장 큰 정점들을 리스트에 저장해 두고, 리스트의 정점이 모두 처리되면 리스트를 다시 계산하거나(이때는 이미 더 낮은 높이의 정점들이 리스트에 추가됩니다), 초과량이 있으면서 더 높은 높이를 가진 새 정점이 나타날 때마다(정점을 relabel한 후) 리스트를 다시 계산하면 됩니다.

이 수정은 간단하지만 복잡도를 크게 줄여 줍니다. 정확히 말하면, 결과 알고리즘의 복잡도는 $O(V E + V^2 \sqrt{E})$이며, 이는 최악의 경우 $O(V^3)$입니다.

이 수정은 1989년에 Cheriyan과 Maheshwari가 제안했습니다.

구현¶

const int inf = 1000000000;

int n;
vector<vector<int>> capacity, flow;
vector<int> height, excess;

void push(int u, int v)
{
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
}

void relabel(int u)
{
    int d = inf;
    for (int i = 0; i < n; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

vector<int> find_max_height_vertices(int s, int t) {
    vector<int> max_height;
    for (int i = 0; i < n; i++) {
        if (i != s && i != t && excess[i] > 0) {
            if (!max_height.empty() && height[i] > height[max_height[0]])
                max_height.clear();
            if (max_height.empty() || height[i] == height[max_height[0]])
                max_height.push_back(i);
        }
    }
    return max_height;
}

int max_flow(int s, int t)
{
    height.assign(n, 0);
    height[s] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[s] = inf;
    for (int i = 0; i < n; i++) {
        if (i != s)
            push(s, i);
    }

    vector<int> current;
    while (!(current = find_max_height_vertices(s, t)).empty()) {
        for (int i : current) {
            bool pushed = false;
            for (int j = 0; j < n && excess[i]; j++) {
                if (capacity[i][j] - flow[i][j] > 0 && height[i] == height[j] + 1) {
                    push(i, j);
                    pushed = true;
                }
            }
            if (!pushed) {
                relabel(i);
                break;
            }
        }
    }

    return excess[t];
}