المپدیا

توجه: برای درک بهتر این الگوریتم بهتر است قسمت قبلی را بخوانید.

در این الگوریتم در شبکه‌ای که به ما داده شده در هر مرحله یک مسیر افزایشی پیدا می‌کنیم سپس مقدار آن مسیر را به اندازه بیشترین ظرفیت ممکن افزایش می‌دهیم. برای پید کردن مسیر افزایشی از روش جست و جو DFS استفاده میکنیم.
منظور از بیشترین نقداری که می‌توان افزایش داد این است که اگر مسیر را به آن مقدار افزایش دهیم دیگر آن مسیر مسیر افزیشی نباشد.

اردر زمانی $O(ef*)$ می‌باشد. که در آن $f*$ اندازه شار بیشینه است. از آن‌جا که در هر مرحله از DFS حداقل یک واحد به شار اضافه می‌شود زمان حداکثر برنامه درست است. حال برای این که بگوییم چرا از این زمان کمتر نمیشود مثال نقضی نشان میدهیم که نشان دهیم اگر الگوریتم DFS بد عمل کند از این بهتر هم نمیشود. با توجه به شکل زیر اگر هر بار یال با ظرفیت یک در مسیر افزایشی بیاید (یک بار مقدارش زیاد شود و بار دیگر کم شود) اندازه مسیر افزایشی پس از هر DFS یک خواهد بود.

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

در این پیاده سازی آرایه دو‌بعدی cap ظرفیت یال‌ها را نشان می‌دهد. آرایه دو بعدی f اندازه جریان هر یال را نشان می‌دهد. گراف به صورت لیست مجاورت به ما داده شده که در آن Gout خروجی راس‌ها و Gin ورودی آن‌ها را ذخیره میکند. همچنین می‌توانستیم از لیشت مجاورت دیگری استفاده کنیم که دو مقدار cap و f را ذخیره کنیم که از حافظه بیهوده جلوگیری کنیم. در اینجا برای فهم راحت‌تر راه‌حل اول را مینویسیم. اگر در برنامه نکته ای استفاده شده باشد به صورت کامنت در جلوی برنامه نوشته شده است.

ford-fulkerson.cpp

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int maxn = 2000; 
int n, m, s, t, flow[maxn][maxn], capacity[maxn][maxn];
vector<int> Gin[maxn], Gout[maxn];
bool vis[maxn];
 
bool dfs(int u){ // agar az rawse u be rawse t masir afzayeshi peyda shavad true mishavad va masir ra 1 vahed ezafe mikonad
    vis[u] = true;
    if(u==t) return true;
    for(int i=0; i<Gout[u].size(); i++){
        int v= Gout[u][i];
        if(vis[v]==false && capacity[u][v]-flow[u][v]>0 && dfs(v)){
            flow[u][v] ++;
            return true;
            /*
            tarjome : agar rawse v dide nashode bood va ghabeliate afzayeshi shodan dasht
            va dfs(v) true shod(yawni az v be t masir vojood dasht) tebghe esteghra 
            masir yek vahed ziad mishavad pas kafi ast yale fewli ra yek vahed ziad konim
            ta hokme esteghra ra bar gharar sazim va sepas return konim
            */
        }
    }
    for(int i=0; i<Gin[u].size(); i++){
        int v=Gin[u][i];
        if(vis[v]==false && flow[u][v]>0 && dfs(v)){
            flow[u][v] --;
            return true;
            //in ghesmate bawdie kar mibashad ke yal haye bargashti tey mishavad
        }
    }
    return false; // agar hich masiri peyda nashod false barmigardanim
}
 
/*
nokte amoozeshi : 
if(a && b && c) -> be tartib a va b va c ra check mikonad va agar har kodam az anha ghalat bashad
baghie ra check nemikonad
hamintor if(a||b||c) be avvalin dorost beresad baghie ra check nemikonad
*/
 
int main(){
    cin >> n >> m >> s >> t;
    s--,t--; //convert to 0 base
    for(int i=0; i<m; i++){
        int u,v,c;
        cin >> u >> v >> c;
        u--,v--;
        capacity[u][v] = c;
        Gout[u].push_back(v);
        Gin[v].push_back(u);
    }
 
    while(dfs(s)){
        fill(vis, vis+n, false);
    }
 
    int flow_size=0;
    for(int i=0; i<n; i++)
        flow_size += flow[s][i];
    cout << flow_size << endl;
 
    return 0;
}