Хамгийн их урсгал - Сайжруулсан түлхэх-дахин шошголох арга¶

Бид илүү сайн ажиллах хугацаанд хүрэхийн тулд түлхэх-дахин шошголох арга-ыг өөрчилнө.

Тайлбар¶

Өөрчлөлт нь туйлын энгийн: Өмнөх өгүүлэлд бид илүүдэлтэй оройг ямар нэг тодорхой дүрэмгүйгээр сонгосон. Гэвч хэрэв бид үргэлж хамгийн их өндөртэй оройнуудыг сонгож, тэдгээр дээр түлхэх ба дахин шошголох үйлдлийг хэрэглэвэл complexity сайжирдаг нь тогтоогддог. Түүнээс гадна хамгийн их өндөртэй оройнуудыг сонгохын тулд бидэнд үнэндээ ямар ч өгөгдлийн бүтэц хэрэггүй — бид хамгийн их өндөртэй оройнуудыг зүгээр л жагсаалтад хадгалж, тэдгээрийг бүгдийг боловсруулсны дараа (тэгвэл аль хэдийн бага өндөртэй болсон оройнууд жагсаалтад нэмэгдэнэ), эсвэл илүүдэлтэй, илүү их өндөртэй шинэ орой гарч ирэх бүрд (орой дахин шошголсны дараа) жагсаалтыг дахин тооцоолно.

Энгийн байдлыг үл харгалзан энэ өөрчлөлт complexity-г ихээхэн бууруулдаг. Тодруулбал үүссэн алгоритмын complexity нь $O(V E + V^2 \sqrt{E})$ бөгөөд хамгийн муу тохиолдолд $O(V^3)$ байна.

Энэ өөрчлөлтийг Чериян ба Махешвари нар 1989 онд санал болгосон.

Implementation¶

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];
}