note: This article comes from the Internet. Please contact me via lethic@163.com if there is any infringement.
lethic@163.com.

1. Maximum Flow: Augmenting Path Algorithms Comparison
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited
2. P321 ( retreat()< or 1. > )
———————————————

distance functionvalid function
1dt= 0
2di<= d(j)+1(rijGx) 1 dii itki= i1-i2-i3...ik+1=t d(i(k)) <= d(i(k+1))+1= d(t)+1=1 d(i(k-1)) <= d(i(k))+1=2 d(i(k-2)) <= d(i(k-1))+1=3 : : d(i(1)) <= d(i(2))+1= k d(i)it 2 rij>0,d(i)= d(j)+1

1rij>0
2pkd(i) = d(j)+1 ds= k
dsskp

3
sap

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

//algorithm shortest augment path;  
void sap()  
    {  
        x =0;  
        obtain the exact distance labels d(i);  
        i = s;  
        while (d(s)<n)  
        {  
            if (i has an admissible arc)  
            {  
                advance(i);  
                if (i == t)  
                {  
                    augment;  
                    i = s;  
                }  
            }  
            else  
                retreat(i);  
        }  
    }  
 
    //procedure advance(i);  
void advance(i)  
    {  
        let(i,j)be an admissible arc in A(t);  
        pre(j) = i;  
        i = j;  
    }  
    //procedure retreat  
void retreat()  
    {  
        d(i) = min(d(j)+1):rij>0;  
        if (i != s)  
            i = pre(i);  
    }
?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

    #include <iostream>  
    #include <cstring>  
    #include <cstdlib>  
 
    usingnamespace std;  
 
    constint Max =225;  
    constint oo =210000000;  
 
    int n,m,c[Max][Max],r[Max][Max],c1[Max][Max],source,sink  
 
    //c1cdis  
int dis[Max];  
 
    void initialize()// dis  
    {  
         int q[Max],head =0, tail =0;//BFS  
         memset(dis,0,sizeof(dis));  
         q[++head] = sink;  
         while(tail < head)  
         {  
             int u = q[++tail], v;  
             for(v =0; v <= sink; v++)  
             {  
                   if(!dis[v] && c1[u][v] >0)  
                   {  
                       dis[v] = dis[u] +1;  
                       q[++head] = v;  
                   }  
             }  
         }  
    }  
 
    int maxflow_sap()  
    {  
        initialize();  
        int top = source, pre[Max], flow =0, i, j, k, low[Max];  
 
        // top  
        memset(low,0,sizeof(low));//low  
while(dis[source] < n)  
        {  
            bool flag =false;  
            low[source] = oo;  
            for(i =0; i <= sink; i++)//  
            {  
                if(r[top][i] >0&& dis[top] == dis[i] +1)  
                {  
                    flag =true;  
                    break;  
                }  
            }  
            if(flag)//   
            {  
                low[i] = r[top][i];  
                if(low[i] > low[top]) low[i] = low[top];//low  
                pre[i] = top; top = i;  
                if(top == sink)//   
                {  
                    flow += low[sink];  
                    j = top;  
                    while(j != source)//   
                    {  
                        k = pre[j];  
                        r[k][j] -= low[sink];  
                        r[j][k] += low[sink];  
                        j = k;  
                    }  
                    top = source;//  
                    memset(low,0,sizeof(low));  
                }  
            }  
            else//   
            {  
                int mindis =10000000;  
                for(j =0; j <= sink; j++)//topdis  
                {  
                    if(r[top][j] >0&& mindis > dis[j] +1)  
                        mindis = dis[j] +1;  
                }  
                dis[top] = mindis;//top  
if(top != source) top = pre[top];//   
            }  
        }  
        return(flow);  
    }

gap

kdi>k,dik?Download sourceCode.cpp