المپدیا

برای بهتر فهمیدن این الگوریتم قضیه شار بیشینه و برش کمینه را مطالعه کنید.

اگر یادتان باشد در شار ورودی و خروجی هر راس به جز ریشه و منبع باید برابر باشند. در این جا ما نیم شار را تعریف می‌کنیم که فرقش با شار این است که ورودی باید بیشتر یا مساوی خروجی باشد. یعنی هر راس مقداری سرریز دارد که به آن excess نیز گفته می‌شود.

در این الگوریتم به هر راس ارتفاعی نسبت می‌دهیم که در ابتدا ارتفاع همه راس‌ها به جر منبع صفر است و ارتفاع منبع $|V|$ می‌باشد. ارتفاع راس منبع و مقصد همواره ثابت است. ارتفاع راس های درخت در یک مرحله درست است اگر شرط زیر برقرار باشد:
اگر از راس u به راس v بتوان شار فرستاد‌ (ظرفیت یال تکمیل نباشد)‌ آنگاه $h[u]\le h[v]+1$

این تابع دو ورودی میگیرد (مانند u و v) به شرطی که اولن ارتفاع راس u بیشتر از v باشد و این که راس u مقدار سرریز داشته باشد و بتواند توسط جهت u به v مقداری از این سرریز را به راس v منتقل کند. تابع push حداکثر مقداری که می‌تواند را منتقل می‌کند. اگر تابع push از تمام ظرفیت یال استفاده کند آن یال را مسدود شده می‌نامیم.

این تابع در ورودی یک راس میگیرد که سرریز دارد و شرایط push را با هیچ راس دیگری ندارد. ارتفاع آن راس را تا جایی بالا می‌برد که قابلیت push با راس دیگری را داشته باشد.

الگوریتم push relabel به سادگی میگوید هر بار عملیات push یا relabel می‌توان جایی انجام داد آن را انجام بده. برای پیاده سازی راحت تر میتوان روی راس ها هر بار پیمایش کرد و اگر راسی سرریز دارد اگر میشود push کرد مقدار سرریز را در غیر این صورت آن راس را relabel میکنیم.

ابتدا بررسی می‌کنیم اگر الگوریتم تمام شود شار بیشینه را به ما می‌دهد یا خیر. برای این کار از چند لم استفاده می‌کنیم :‌

پس از هر عملیات push و relabel ارتفاع راس ها مقداری درست می‌مانند.

به وضوح عملیات push این شرایط را به هم نمیزند چون روی ارتفاع بالاتر به پایین‌تر انجام می‌شود. عملیات relabel نیز نمی‌تواند مشکلی ایجاد کند چرا که از آنجا که وقتی یک راس را می‌خواهیم relabel کنیم شرایط push با هیچ راسی با ارتفاع پایین تر را نخواهد داشت و پس از relabel فقط شرایط push با یک ارتفاع پایین‌ترش را می‌تواند داشته باشد.

اگر الگوریتم تمام شود شار داده شده بیشینه است.

برای این کار کافی‌ست نشان دهیم مسیر افزایشی‌ای نمی‌تواند وجود داشته باشد. فرض کنید مسیری از راس منبع به مقصد وجود دارد. آن مسیر را با $v_1, v_2, ..., v_k$ نشان می‌دیهم به طوری که $v_1$ راس منبع و $v_k$ راس مقصد باشد. طبق تعریف ارتفاع درست اگر ارتفاع راس ها درست باشد میدانیم $h[v_1]\le h[v_2]+1$ همچنین میانیم به ازای هر $i$ ($1\le i<k$) داریم $h[v_i]\le h[v_{i+1}]+1$ در نتیجه میتوان با استقرا نشان داد $h[v_1]\le h[v_k]+k-1$ که نشان می‌دهد ارتفاع راس منبع نمی‌تواند بیش از ‌k واحد با مقصد اختلاف داشته باشد که درست نیست چرا که k همواره کمتر از تعداد راس هاست و ارتفاع راس منبع v واحد بیشتر از مقصد است. پس خروجی برنامه صحیح است.
حال میخواهیم نشان دهیم برنامه حتمن تمام میشود. برای این کار ابتدا نشان می‌دهیم اگر ارتفاع هر راس از $2v$ بیشتر نمیشود.

اگر راس $v$ مقدار سرریز داشته باشد، حتمن مسیر افزایشی ای به راس منبع دارد (توجه کنید مسیر افزایشی از راس v به راس منبع است.)

فرض کنید جریان ها یک واحد یک واحد در یال ها اضافه شده‌اند،‌ یعنی تابع push به جای این که همه‌ی آبی که می‌تواند را جابجا کند یک واحد یک واحد آب جابجا کند. در یال‌برگشتی هم کاری که می‌کنیم واحد های آب اضافی سرریز را به راس قبلی برمی‌گردانیم، حال هر واحد شار در راسی که سرریز دارد یک مسیر از راس منبع ب آن راس است. اگر یک مسیر از راس منبع به یک راسی داشته باشیم و جریان را توسط آن یک واحد اضافه کنیم برعکس این مسیر هم مسیر افزایشی‌ست.

ارتفاع هیچ راسی از $2n-1$ بیشتر نمی‌شود.

برای اثبات این مسئله از لم ۳ کمک میگیریم. فرض می‌کنیم ارتفاع راسی بیشتر از $2n-1$ شد در نتیجه مسیر نیم‌افزایشی از آن راس به راس منبع وجود دارد (مسیر نیم‌افزایشی مسیری است که تمام یال‌هایش ظرفیت اضافه شدن در جهت مسیر را داشته باشند. حال از اثبات لم ۲ می‌توان نتیجه گرفت اگر هر دو راسی به هم مسیر نیم‌افزایشی داشته باشند ارتفاعشان نمی‌تواند بیش از $n-1$ واحد اختلاف داشته باشد. از آنجا که راس در نظر گرفته شده ارتفاعش $2n$ است و n واحد اختلاف دارد پس به تناقض می‌رسیم.

با توجه به لم چهار بدیهتن می‌توان نشان داد هر راس حداکثر 2n بار relabel می‌شود پس در مجموع $2n^2$ عمل relabel داریم که هرکدام زمانشان $O(n)$ است پس همه relabel ها باهم زمان $O(n^3)$ می‌برند.

در بین هر دو عمل relabel روی رئوس تعداد push های مسدود کننده حداکثر $e$ تاست.

بدیهتن اگر یالی مسدود شود نمیتواند در جهت دیگرش push شود تا از مسدودیت در بیاید پس هر یال تا عمل relabel صورت نگیرد حداکثر یک بار مسدود می‌شود.

تعداد push های مسدود کننده درمجموع $2ve$ تاست.

برای این کار به ازای هر یال به مسئله نگاه میکنیم. هر یال اگر یک بار ظرفیتش تکمیل شود تا ارتفاع راس دیگرش حداقل دو واحد زیاد نشود نمیتواند دوباره ظرفیتش تکمیل شود. پس حداکثر $2ve$ بار یال ها توسط این دستور مسدود می‌شوند.

تعداد push های غیر مسدود کننده حداکثر $4v^2(v+e)$ می‌باشند.

تابع $\phi$ را اینگونه تعریف میکنیم که $\phi = \sum_{u|excess[u]>0}h[u]$ حال با استفاده از تغییرات $\phi$ نشان می‌دهیم این مقدار درست است. اگر عملیات relabel انجام دهیم از آنجا که ارتفاع راس زیاد می‌شود مقدار $\phi$ را حداکثر $2n$ واحد زیاد می‌کند. از انجا که ارتفاع راس‌ها حداکثر $2n$ می‌شود پس در مجموع relabel ها مقدار این عدد را $4n^2$ زیاد می‌کند. حال تاثیر push های مسدود کننده را در نظر می‌گیریم. هر ‌‌‌push مسدود کننده حداکثر به اندازه راس پایین‌تر به عددمان اضافه می‌کند پس در کل $4ev^2$ می‌شود. حال هر بار push غیر مسدود کننده می‌دهیم حتمن سرریز راس بالایی صفر می‌شود و سرریز راس پایین تر ممکن است اضافه شود پس $\phi$ حداقل یک واحد کم می‌شود. پس حداکثر به اندازه جوابی که گفتیم تغییر می‌کند.

برای تحلیل زمانی کافی است به لم های قسمت قبل نگاه کنیم. در مجموع کار هایی که می‌‌کنیم از $O(v^2e)$ می‌شود.

در پیاده‌سازی این الگوریتم می‌توان فرض کرد یال چندگانه و دوطرفه وجود دارد، اما برای راحتی برنامه فرض می‌کنیم فقط در یک جهت وجود دارد.

push-relabel.cpp

#include <iostream>
#include <vector>
 
using namespace std;
 
const int maxn = 100; // agar tewdad yal ha km bashad ta 300 niz javab midahad
int n, m, s, t, excess[maxn], flow[maxn][maxn], capacity[maxn][maxn], h[maxn];
vector<int> G[maxn];
 
void push(int u, int v){
    int amount = min(excess[u] , capacity[u][v]-flow[u][v]);
    excess[u] -= amount;
    excess[v] += amount;
    flow[u][v] += amount;
    flow[v][u] -= amount;
}
 
void relabel(int u){
    int newheight = 2*n-1;
    for(int v=0; v<n; v++){
        if (capacity[v] - flow[v] > 0) newheight = min(newheight, h[v]+1);
    }
    h[u] = newheight;
}
 
int main(){
    cin >> n >> m >> s >> t;
    s--, t--;
    for(int i=0; i<m;i ++){
        int u, v, cap;
        cin >> u >> v >> cap;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
        capacity[u][v] = cap;
    }
 
    for(int i=0; i<n; i ++){
        excess[s] = capacity[s][i]; // az anja ke hame push mishavand excess in raws 0 mimanad
        push(s,i);
    }
    h[s] = n;
 
    bool cntinue = true;
    while(cntinue){
        bool next = false;
        for(int u=0; u<n; u++){
            if(u==s || u==t) continue;
            if(excess[u] > 0){
                next = true;
                for(int i=0; i<G[u].size(); i++){
                    int v=G[u][i];
                    if(h[u] > h[v]) push(u,v) ; // agar available nabashad hichi push nemishavad
                }
                if(excess[u] > 0) relabel(u); // agar excess hanooz mosbat bood digar pushi nadarim
            }
        }
        cntinue = next;
    }
 
    cout << excess[t] << endl; // dar in ja excess[t] andaze shar bishine ast zira hich gah t ra push nemikonim
    return 0;
}