第一种是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[i] = 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[i] > n && c[i][hd] > 0){ q[qe++] = i; level[i] = level[hd] + 1; gap[ level[i] ] ++; } } } } int find_path(int u){ for(int i = 0; i < n; i ++) if(c[u][i] > 0 && level[u] == level[i] + 1) return i; return -1; } int relabel(int u){ int tmp = inf; for(int i = 0; i < n; i ++) if(c[u][i] > 0 && tmp > level[i] + 1) tmp = level[i] + 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[s] < 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[i]) if(min_flow > c[ pre[i] ][i]) min_flow = c[ pre[i] ][i]; for(int i = t; i != s; i = pre[i]){ c[ pre[i] ][i] -= min_flow;//正向减 c[i][ pre[i] ] += min_flow; } flow += min_flow; u = s;//重新从源点找 } }else{//找不到弧 if( -- gap[ level[u] ] == 0) return flow;//更新断层 + 判断是否断层 v = relabel(u); gap[v] ++; level[u] = v;//重新标号 if(u != s) u = pre[u];//当前弧优化 } } 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[u][v] = w; } for(int i = 0; i < np; i ++){ int v, w; scanf(" (%d)%d", &v, &w); c[s][v] = w; } for(int i = 0; i < nc; i ++){ int u, w; scanf(" (%d)%d", &u, &w); c[u][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] = s, v; int flow = 0; int aug = inf; gap[s] = t;// gap[0] = n, gap[s] = t while(level[s] < n){ for(v = cur[u]; v < n; v ++){ if(c[u][v] > 0 && level[u] == level[v] + 1) break; } if(v < n){ pre[v] = u; if(aug > c[u][v]) aug = c[u][v]; u = cur[u] = 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[u][v] > 0 && min_label > level[v]){ cur[u] = v; min_label = level[v]; } } if(--gap[level[u]] == 0) return flow; level[u] = min_label + 1; gap[ level[u] ] ++; u = pre[u]; } } 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[u][v] = w; } for(int i = 0; i < np; i ++){ int v, w; scanf(" (%d)%d", &v, &w); c[s][v] = w; } for(int i = 0; i < nc; i ++){ int u, w; scanf(" (%d)%d", &u, &w); c[u][t] = w; } int flow = sap(); printf("%d\n", flow); } return 0; }
最后一种就是邻接表的SAP，也是看HH博客写的。。。
注意引用的用法。。。
list不过我不明白gap初始化的情况啊。。。
还有relabel的过程也不是很理解。。。。
再理解理解吧