المپدیا

برای بهتر فهمیدن این قسمت بهتر است قسمت قبلی را خوانده باشید.

در این بخش می‌خواهیم کار قسمت قبل را انجام دهیم تنها تفاوت کار اینجاست که در این قسمت از BFS به جای DFS استفاده میکنیم و کوتاه‌ترین مسیر افزایشی را در هر مرحله تا جایی که می‌توانم زیاد می‌کنیم (دقت کنید که منظور از کوتاه‌ترین از نظر تعداد یال است نه اندازه‌ی یال‌ها).

می‌خواهیم نشان دهم اردر زمانی این قسمت $O(e^2v)$ می‌باشد.
توجه کنید یال رو به جلو را یالی تعریف می‌کنیم که جهتش با جهت مسیر یکی باشد (از منبع دور شود) و یال رو به عقب را یالی تعریف می‌کنیم که جهتش رو به منبع باشد. می‌دانیم هر یال در هر دو جهتش می‌تواند در مسیر افزایشی شرکت کند. یک جهت یک یال را قابل استفاده می‌گوییم اگر در آن جهت بتوان آن یال را در مسیر افزایشی شرکت داد. در هنگام پیاده‌سازی الگوریتم BFS فقط در یال‌هایی می‌رویم که از آن جهت قابل استفاده باشند‌ (توجه کنید وقتی یالی در یک جهتش بتواند عضو درخت BFS باشد در جهت دیگرش نمی‌تواند عضو درخت BFS باشد. با مفهوم کوتاه‌ترین فاصله به مشکل می‌خورد.). از آنجا که در هر BFS مسیر افزایشی را تا جایی که می‌توانیم زیاد می‌کنیم،‌ یکی از یال‌ها در جهتی که در درخت آمده بلااستفاده می‌شود،‌ به این صورت که یا در جهت موافق خودش آمده و ظرفیتش تکمیل می‌شود یا در جهت مخالف خودش آمده و ظرفیتش صفر می‌شود. به‌طور دقیق تر پس از هر بار BFS و اضافه کردن مسیر افزایشی برای هر یال حداقل یکی از سه اتفاق زیر رخ می‌دهد.
الف) آن یال در جهتی که در مسیر اضافه شده است بلااستفاده می‌شود،‌ یعنی اگر در جهت موافق خودش باشد ظرفیتش تکمیل می‌شود و اگر در جهت مخالف خودش باشد جریانش صفر می‌شود. در این حالت کوتاه‌ترین مسیر دو سر این یال یا تغییر نمی‌کند یا بیشتر می‌شود (به بیان دیگر این یال پس از بلا استفاده شدند مسیر کوتاه‌تری به وجود نمی‌آورد)
ب) یال در جهت برعکسی که در مسیر آمده‌است بلااستفاده بوده و اکنون قابل استفاده می‌شود. یعنی اگر در جهت موافق اضافه شده است جریانش صفر بوده که پس از اضافه شدن از جهت دیگر قابل استفاده می‌شود یا اگر در جهت مخالف باشد جریانش تکمیل بوده که پس از کم شدن در جهت دیگر دوباره قابل استفاده می‌شود. از آنجا که جهت دیگر این یال ها از ارتفاع بیشتر ‌BFS به ارتفاع کمتر آمده‌اند قابل استفاده شدنشان طول مسیری را کم نمی‌کند اگر یادتان باشد گفته بودیم اگر یال در یک جهتش در درخت استفاده شود در جهت دیگر نمیتواند استفاده شود.
ج) ممکن است برای یک یال هیچ کدام از اتفاقات بالا رخ ندهد.
از آنجا که در هر مرحله از الگوریتم یک یال بلااستفاده میشود و تعدادی یال ممکن است قابل استفاده شوند بهتر است بشماریم هر یال حداکثر چند بار ممکن است قابل استفاده شود،‌ اگر هر یال حداکثر v بار قابل استفاده شود از آنجا که e یال داریم در طی مراحل ev یال قابل استفاده داریم برای غیر قابل استفاده کردن هر کدام از آنها باید $O(e)$ در یک BFS مصرف کنیم در این صورت زمان اجرایی برنامه ما $O(e^2v)$ می‌شود.
حال کافی‌ست ثابت کنیم هر یال فقط n بار می‌تواند قابل استفاده باشد. با استفاده از سه حالت ذکر شده می‌توانیم نتیجه بگیریم هیچ راسی فاصله‌اش تا ریشه کمتر نمی‌شود. در نتیجه اگر یالی قابل استفاده شود در حالت دو از آنجا که جهتی که در آن قابل استفاده می‌شود از ارتفاع زیاد به کم است باید ارتفاع کممان حداقل دو واحد در طی الگوریتم بیشتر شود تا بتواند دوباره غیرقابل استفاده شود. از آنجا که به ازای هر یال ارتفاع دو طرفش در مجموع ۲n واحد تغییر می‌کند و برای این که دوباره در یک جهت بلااستفاده شود باید ۲ بار در مجموع ارتفعشان تغییر کند هر یال حداکثر n بار بلااستفاده می‌شود پس اردر گفته شده برای مسئله درست است.

این الگوریتم زمانش چندجمله‌ای می‌باشد. با توجه به تحلیل زمانیِ، این الگوریتم نه تنها بهتر از الگوریتم قبلی می‌باشد بلکه بدترین حالت این الگوریتم به احتمال کمی رخ می‌دهد. از آنجا که هر راسی در طول اجرای الگوریتم شاید تغییر ارتفاع زیادی ندهد یا همه راس ها که نمی‌توانند به ارتفاع n برسند در هر ارتفاع حداقل باید یک راس باشد. پس اردر گفته شده ضریب خیلی خوبی دارد و برای گراف های ۲۰۰ راسی و حتی ۳۰۰ (در صورتی که کم یال باشد) به خوبی کار می‌کند و سریع تر از الگوریتم های دیگر است. چندگانگی یال ها و وجود یال در هر جهت برای این الگوریتم تاثیر گذار نیست اما برای راحتی پیاده سازی در اینجا فرض کردیم حداکثر در یک جهت یال وجود دارد.

در الگوریتم از آنجا که بین هر دو راس حداکثر یک یال وجود دارد (با توجه به فرض)‌ می‌توانیم به این صورت عمل کنیم که اگر یالی از راس u به v وجود داشت که ظرفیتش c بود،‌ ظرفیت u به v را برابر c قرار دهیم و ظرفیت v به u را برابر صفر قرار دهیم، مقدار شار از u به v را منفی شده‌ی مقدار شار یال قرار دهیم. با این فرض ها اختلاف بین ظرفیت و جریان یک یال در هر جهتش حداکثر جریان قابل استفاده در آن جهت را به ما می‌دهد.
توجه کنید که اگر بخواهید می‌توانید برای ظرفیت و شار دو لیست مجاورت بگیرید و یال‌های گراف را در هر دو جهت ذخیره کنید که فضای حافظه کمتری بگیرید و محدودیتی در ورودی نداشته باشید اینجا برای راحتی کار اینگونه عمل نکردیم.

edmonds-karp.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue> 
 
using namespace std;
 
const int maxn=300;//agar graph por yal nabashad ta 400 ham javab midahad
int n, m, s, t, flow[maxn][maxn], capacity[maxn][maxn], par[maxn];
vector<int> G[maxn];
bool vis[maxn];
 
bool bfs(int s){ // masir afzayeshi ra ezafe ham mikonad
    fill(vis, vis+n, 0);
    fill(par, par+n, -1);
    vis[s] = true;
    queue<int> qu;
    qu.push(s);
 
    while(qu.size()>0){
        int u = qu.front();
        qu.pop();
        for(int i=0; i<G[u].size(); i++){
            int v=G[u][i];
           if(vis[v] == false && capacity[u][v]-flow[u][v] > 0){
               // ba tavajjoh be manfi boodane flow dar halate barax va 0 boodane capacity dar in halat meghdare bala dar har halati hadde axar mizane ezafe shodan ra midahad
               vis[v] = true;
               qu.push(v);
               par[v] = u;
           }
        }
    }
    if(par[t]==-1) return false;
    vector<int> path;
    int k=t;
    path.push_back(k);
    while(k!=s){
        k=par[k];
        path.push_back(k);
    }
 
    reverse(path.begin(), path.end());
    int minimum;// mohasebe meghdari ke mitavan be flow ezafe kard
    for(int i=0; i<path.size()-1; i++){
        int u=path[i], v=path[i+1];
        if(i==0) minimum = capacity[u][v] - flow[u][v];
        else minimum = min(minimum, capacity[u][v]-flow[u][v]);
    }
 
    //ezafe kardane masire morede nazar
    for(int i=0; i<path.size()-1; i++){
        int u=path[i], v=path[i+1];
        flow[u][v] += minimum;
        flow[v][u] -= minimum;
        // agar tavajjoh konid in kar baraye yal haye barax niz tori ke mikhahim natije midahad
    }
    return true;
}
 
int main(){
    cin >> n >> m >> s >> t;
    for(int i=0; i<m; i++){
        int u,v,cap;
        cin >> u >> v >> cap;
        u--, v--;
        capacity[u][v] = cap;
        G[u].push_back(v);
        G[v].push_back(u); // tavajjoh dashte bashid ke ma har 2 taraf ra be liste mojaverat ezafe mikonim
        //dar bfs daghigh tar karborde in kar ra mibinid
    }
 
    while(bfs(s));
 
    int flowsize=0;
    for(int u=0; u<n; u++) 
        flowsize += flow[s][u];
    cout << flowsize << endl;
    return 0;
}