poj_1459，sap的三种写法

demn

　　第一种是BFS的SAP


bfs+sap


#include<cstdio>
#include<cstring>
using namespace std;

const int inf = 100000000;//不要开太大
int n, np, nc, m;
const int maxn = 105;
int c[maxn][maxn];//残留网络
int s, t;
int level[maxn], gap[maxn];//层次网络， 层结点数（用于间隙优化）
int q[maxn], pre[maxn];//队列， 前驱
void init_sap(){
memset(level, 10, sizeof level);
//for(int i = 0; i <= n ;i ++) level = n + 1;
memset(gap, 0, sizeof gap);
int qs = 0, qe = 0;
q[qe++] = t;
level[t] = 0;
gap[ level[t] ] ++;
while(qs < qe){
int hd = q[qs++];
for(int i = 0; i < n; i ++){
if(level > n && c[hd] > 0){
q[qe++] = i;
level = level[hd] + 1;
gap[ level ] ++;
}
}
}
}
int find_path(int u){
for(int i = 0; i < n; i ++)
if(c > 0 && level == level + 1) return i;
return -1;
}
int relabel(int u){
int tmp = inf;
for(int i = 0; i < n; i ++)
if(c > 0 && tmp > level + 1)
tmp = level + 1;
if(tmp == inf) tmp = n;
return tmp;
}
int sap(){
init_sap();
int flow = 0;
int u = s;
memset(pre, -1, sizeof pre);
while(level < n){
int v = find_path(u);//寻找允许弧
if(v >= 0){
pre[v] = u;
u = v;
if(u == t){//找到完整增广路
int min_flow = inf;
for(int i = t; i != s; i = pre)
if(min_flow > c[ pre ]) min_flow = c[ pre ];
for(int i = t; i != s; i = pre){
c[ pre ] -= min_flow;//正向减
c[ pre ] += min_flow;
}
flow += min_flow;
u = s;//重新从源点找
            }
}else{//找不到弧
if( -- gap[ level ] == 0) return flow;//更新断层 + 判断是否断层
v = relabel(u);
gap[v] ++;
level = v;//重新标号
if(u != s)
u = pre;//当前弧优化
        }
}
return flow;
}
int main(){
while(~scanf("%d%d%d%d", &n, &np, &nc, &m)){
memset(c, 0, sizeof c);
s = n, t = n + 1, n += 2;
for(int i = 0; i < m; i ++){
int u, v, w;
scanf(" (%d,%d)%d", &u, &v, &w);
c[v] = w;
}
for(int i = 0; i < np; i ++){
int v, w;
scanf(" (%d)%d", &v, &w);
c[v] = w;
}
for(int i = 0; i < nc; i ++){
int u, w;
scanf(" (%d)%d", &u, &w);
c[t] = w;
}
int flow = sap();
printf("%d\n", flow);
}
return 0;
}
　　第二种就是普通的矩阵SAP，看着HH博客里的写的。。


matrix


#include<cstdio>
#include<cstring>
using namespace std;

const int inf = 100000000;//不要开太大
int n, np, nc, m;
const int maxn = 105;
int c[maxn][maxn];//残留网络
int s, t;
int level[maxn], gap[maxn];//层次网络， 层结点数（用于间隙优化）
int cur[maxn], pre[maxn];
int sap(){
memset(cur, 0, sizeof cur);
memset(level, 0, sizeof level);
memset(gap, 0, sizeof gap);
int u = pre = s, v;
int flow = 0;
int aug = inf;
gap = t;// gap[0] = n, gap = t
while(level < n){
for(v = cur; v < n; v ++){
if(c[v] > 0 && level == level[v] + 1)
break;
}
if(v < n){
pre[v] = u;
if(aug > c[v]) aug = c[v];
u = cur = v;
if(u == t){
flow += aug;
for(v = t; v != s; v = pre[v]){
c[ pre[v] ][v] -= aug;
c[v][ pre[v] ] += aug;
}
aug = inf, u = s;
}
}else{
int min_label = n;
for(v = 0; v < n; v ++){
if(c[v] > 0 && min_label > level[v]){
cur = v;
min_label = level[v];
}
}
if(--gap[level] == 0) return flow;
level = min_label + 1;
gap[ level ] ++;
u = pre;
}
}
return flow;
}
int main(){
while(~scanf("%d%d%d%d", &n, &np, &nc, &m)){
memset(c, 0, sizeof c);
s = n, t = n + 1, n += 2;
for(int i = 0; i < m; i ++){
int u, v, w;
scanf(" (%d,%d)%d", &u, &v, &w);
c[v] = w;
}
for(int i = 0; i < np; i ++){
int v, w;
scanf(" (%d)%d", &v, &w);
c[v] = w;
}
for(int i = 0; i < nc; i ++){
int u, w;
scanf(" (%d)%d", &u, &w);
c[t] = w;
}
int flow = sap();
printf("%d\n", flow);
}
return 0;
}
　　最后一种就是邻接表的SAP，也是看HH博客写的。。。
　　注意引用的用法。。。


list　　不过我不明白gap初始化的情况啊。。。
　　还有relabel的过程也不是很理解。。。。
　　再理解理解吧