poj_1459，sap的三种写法
第一种是BFS的SAPbfs+sap
#include<cstdio>
#include<cstring>
using namespace std;
const int inf = 100000000;//不要开太大
int n, np, nc, m;
const int maxn = 105;
int c;//残留网络
int s, t;
int level, gap;//层次网络， 层结点数（用于间隙优化）
int q, pre;//队列， 前驱
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 = t;
level = 0;
gap[ level ] ++;
while(qs < qe){
int hd = q;
for(int i = 0; i < n; i ++){
if(level > n && c > 0){
q = i;
level = level + 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 = 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 ++;
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 = w;
}
for(int i = 0; i < np; i ++){
int v, w;
scanf(" (%d)%d", &v, &w);
c = w;
}
for(int i = 0; i < nc; i ++){
int u, w;
scanf(" (%d)%d", &u, &w);
c = 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;//残留网络
int s, t;
int level, gap;//层次网络， 层结点数（用于间隙优化）
int cur, pre;
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 = n, gap = t
while(level < n){
for(v = cur; v < n; v ++){
if(c > 0 && level == level + 1)
break;
}
if(v < n){
pre = u;
if(aug > c) aug = c;
u = cur = v;
if(u == t){
flow += aug;
for(v = t; v != s; v = pre){
c[ pre ] -= aug;
c[ pre ] += aug;
}
aug = inf, u = s;
}
}else{
int min_label = n;
for(v = 0; v < n; v ++){
if(c > 0 && min_label > level){
cur = v;
min_label = level;
}
}
if(--gap] == 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 = w;
}
for(int i = 0; i < np; i ++){
int v, w;
scanf(" (%d)%d", &v, &w);
c = w;
}
for(int i = 0; i < nc; i ++){
int u, w;
scanf(" (%d)%d", &u, &w);
c = w;
}
int flow = sap();
printf("%d\n", flow);
}
return 0;
}
最后一种就是邻接表的SAP，也是看HH博客写的。。。
注意引用的用法。。。
list 不过我不明白gap初始化的情况啊。。。
还有relabel的过程也不是很理解。。。。
再理解理解吧
页:
[1]