网络流新进展！SAP算法！模板具体分析！

车皮

　　Dinic虽然还没理解清楚！EK也只是马马虎虎！现在就来讲SAP！可能时候未到！不过也要多学习！
　　现在附上SAP代码和具体分析！应该对想学习的同学有帮助吧！



typedef struct node{
int v, w;
struct node *nxt, *op;
}NODE;
NODE edg[MM]; // 保存所有的边
NODE *link[NN]; // 记录节点所在链表的首节点
int h[NN];    // 距离标号，记录每个点到汇点的距离，这里的距离指的是层数
int num[NN];  // gap优化，标号为i的顶点个数
int M, N, idx, S, T, n; // S 表示源点，T表示汇点，n表示节点个数
void add(int u, int v, int c){
idx++;
edg[idx].v = v;
edg[idx].w = c;
edg[idx].nxt = link;
edg[idx].op = edg + idx + 1;
link = edg + idx;     
idx++;
edg[idx].v = u;
edg[idx].w = 0;
edg[idx].nxt = link[v];
edg[idx].op = edg + idx - 1;
link[v] = 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[p->v] + 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[S] == n) return flow - l; // gap
}
// 这里是有剩余容量的可行边
if (p->w > 0 && h[p->v] < tmp){
tmp = h[p->v];  
}
}
if(l == flow){//  如果没有找到增流，才修改标号，刚开始写错了，也杯具的过了好多题
num[h]--;   // gap
if (num[h] == 0) h[S] = n; // gap，每个点的距离值最多为n - 1，这里设为n 表示断层了
else{
h = tmp + 1;
num[h]++;   // gap
}
}
return flow - l;
}
/*n表示总点的个数，包括源点和汇点*/
void sap(){
int ans = 0;
memset(h, 0, sizeof(h)); // h 保存的是距离标号(到汇点的)
memset(num, 0, sizeof(num));
num[0] = n;
while(h[S] < n){
ans += aug(S, INF);
}
printf("%d\n", ans);
}