鬼泣 发表于 2015-9-18 07:37:09

最大流 sap用法 和 模板

typedef struct node{
int v, w;
struct node *nxt, *op;
}NODE;
NODE edg; // 保存所有的边
NODE *link; // 记录节点所在链表的首节点
int h;    // 距离标号,记录每个点到汇点的距离,这里的距离指的是层数
int num;// gap优化,标号为i的顶点个数
int M, N, idx, S, T, n; // S 表示源点,T表示汇点,n表示节点个数
void add(int u, int v, int c){
idx++;
edg.v = v;
edg.w = c;
edg.nxt = link;
edg.op = edg + idx + 1;
link = edg + idx;   
idx++;
edg.v = u;
edg.w = 0;
edg.nxt = link;
edg.op = edg + idx - 1;
link = edg + idx;
}
int Min(int a, int b){
return a < b ? a : b;
}
int aug(int u, int flow){
if (u == T) return flow;
int l = flow;// l表示剩余容量
int tmp = n - 1;
for (NODE *p = link; p; p = p->nxt){
if (h == h + 1 && p->w){
int f = aug(p->v, Min(l, p->w));
l -= f;
p->w -= f;
p->op->w += f;
if (l == 0 || h == n) return flow - l; // gap
}
// 这里是有剩余容量的可行边
if (p->w > 0 && h < tmp){
tmp = h;
}
}
if(l == flow){//如果没有找到增流,才修改标号,刚开始写错了,也杯具的过了好多题
num]--;   // gap
if (num] == 0) h = n; // gap,每个点的距离值最多为n - 1,这里设为n 表示断层了
else{
h = tmp + 1;
num]++;   // gap
}
}
return flow - l;
}
/*n表示总点的个数,包括源点和汇点*/
void sap(){
int ans = 0;
memset(h, 0, sizeof(h)); // h 保存的是距离标号(到汇点的)
memset(num, 0, sizeof(num));
num = n;
while(h < n){
ans += aug(S, INF);
}
printf("%d\n", ans);
}
  
  sap里面有个gap优化,一直没看懂,今天整理一下,发现被我修改变量名的num记录的含义是标号为i的顶点数,刚开始num数组置零,表示所有表号都没有,唯独num = n,表示所有的顶点现在的标号都为0。引用一下:我们在某次增广后,最大流可能已经求出,因此算法做了许多无用功。可以发现,距离标号是单调增的。这启示我们如果标号中存在“间隙”,则图中不会再有可增广路,于是算法提前终止。实践中我们使用数组vh记录标号为i的顶点个数,若重标号使得vh中原标号项变为0,则停止算法。我这里用的num存的。
页: [1]
查看完整版本: 最大流 sap用法 和 模板