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

 ```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)0; if (i != s) i = pre(i); }```
 ```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 #include #include   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