Algorithm: Thuật toán luồng cực đại trên mạng

Mạng là đồ thị có hướng G = (V, E) trong đó có duy nhất 1 đỉnh A không có cung đi vào và duy nhất 1 đỉnh B không có cung đi ra và mỗi cung của nó có trọng số không âm.

Luồng là phép gán trọng số mỗi cạnh trong mạng bởi 1 số không âm nhỏ hơn trọng số đó và sao cho tổng giá trị nối vào 1 đỉnh bằng tổng giá trị đi ra khỏi đỉnh đó.

Giá trị của 1 luồng là tổng luồng trên các cung đi ra đỉnh phát A ( hoặc thu B).

Luồng cực đại là luồng có giá trị lớn nhất.

Lát cắt, đường tăng luồng, định lý Ford – Fulkerson

Lát cắt (X, Y) là cách phân các tập đỉnh của mạng thành 2 tập X, Y trong đó X chứa đỉnh phát A và Y chứa đỉnh thu B. Khả năng thông qua của lát cắt là tổng trọng số các cạnh (u, v) với u thuộc X và v thuộc Y.

Định lý Ford-Fulkerson: Lát cắt nhỏ nhất (hẹp nhất) chính là giá trị của luồng cực đại.

Thuật toán: với f là một luồng trong mạng G(V, E).

Xây dựng đồ thị tăng luồng Gf(V, Ef):

Nếu f[u, v] < c[u, v] thì thêm (u, v) vào Ef với trọng số c[u, v] – f[u, v] (cung thuận) chỉ khả năng tăng luồng trên cung (u, v).
Nếu f[u, v] > 0 thì thêm cung (v, u) vào Ef với trọng số f[u, v] (cung nghịch) chỉ khả năng giảm luồng trên cung (u, v).

2. Tìm đường đi cơ bản từ A B trên đồ thị Gf. Gọi Delta là giá trị nhỏ nhất trên đường đi và đặt

f[u, v] = f[u, v] + Delta nếu (u, v) nằm trên đường đi và là cung thuận.
f[u, v] = f[u, v] - Delta nếu (u, v) nằm trên đường đi và là cung nghịch.

Khi đó giá trị luồng f tăng Delta so với luồng cũ và đường đi tìm được gọi là đường tăng luồng
Tiến hành thực hiện đường tăng luồng cho đến khi không tăng được nữa. Đồ thị f kết quả chính là luồng cực đại cần tìm.

Vậy các bước cụ thể tìm luồng cực đại trên mạng:

Khởi tạo luồng 0
Tìm đường đi cơ bản từ A B trên đồ thị tăng luồng (đường tăng luồng), cập nhật lại kết quả f và Gf, lặp lại bước này cho đến khi không tìm được nữa.
Xuất kết quả luồng cực đại tìm được.

Code luồng cực đại dùng định lý Ford - Fulkerson:

#include <stdio.h>
#define ma 1002
long long n,m,s,t,a[ma][ma]={0},max_flow=0,trace[ma][2],current[ma][ma]={0};
void scan_input()
{
    long long i,u,v,c;
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for (i=0;i<m;i++)
    {
        scanf("%lld%lld%lld",&u,&v,&c);
        a[u][v]+=c;
    }
}
long long mi(long long value1, long long value2)
{
    return value1>value2?value2:value1;
}
bool find_path()
{
    long long free[ma],que[ma],i,fron=-1,rear=0;
    for (i=1;i<=n;i++) free[i]=0;
    que[rear]=s;
    trace[s][1]=ma;
    free[s]=1;
    while (fron<rear)
    {
        fron++;
        for (i=1;i<=n;i++)
            if (free[i]==0 && (a[que[fron]][i]>0 || current[i][que[fron]]>0))
            {
                rear++;
                que[rear]=i;
                free[i]=1;
                trace[i][0]=que[fron];
                if (a[que[fron]][i]==0) trace[i][0]=-trace[i][0];
                if (a[que[fron]][i]>0) trace[i][1]=mi(a[que[fron]][i],trace[que[fron]][1]);
                else trace[i][1]=mi(current[i][que[fron]],trace[que[fron]][1]);
                if (i==t) return true;
            }
    }
    return false;
}
void increase_flow()
{
    long long i=t,min_value=trace[i][1];
    while (i!=s)
    {
        if (trace[i][0]>0)
        {
            a[trace[i][0]][i]-=min_value;
            current[trace[i][0]][i]+=min_value;
        }
        else
        {
            a[i][-trace[i][0]]+=min_value;
            current[i][-trace[i][0]]-=min_value;
        }
        i=trace[i][0]>0?trace[i][0]:-trace[i][0];
    }
}
void print_result()
{
    long long i;
    for (i=1;i<=n;i++)
        if (current[s][i]>0) max_flow+=current[s][i];
    printf("%lld",max_flow);
}
int main()
{
    scan_input();
    while (find_path()) increase_flow();
    print_result();
    return 0;
}

Tham khảo: >> Giải thuật và lập trình - Trang 257
                 >> Competitive programming 3 - Trang 163
Bài tập:
1. UVa 00259 - Software Allocation    Code(Submitted 16-06-2017)
2. UVa 00820 - Internet Bandwidth Code(Submitted 17-06-2017)
3. UVa 10092 - The Problem with the ...        Code(Submitted 17-06-2017)
4. UVa 10511 - Councilling    Code(Submitted 27-06-2017)
5. UVa 10779 - Collectors Problem               Code(Submitted 28-06-2017)
6. UVa 11045 - My T-Shirt Suits Me
7. UVa 11167 - Monkeys in the Emei ...
8. UVa 11418 - Clever Naming Patterns
9.   UVa 10330 - Power Transmission
10. UVa 10480 - Sabotage
11. UVa 11380 - Down Went The Titanic
12. UVa 11506 - Angry Programmer
13. UVa 12125 - March of the Penguins

Algorithm

Bài viết mới

Tuesday, March 22, 2016

Thuật toán luồng cực đại trên mạng

No comments:

Post a Comment