首页 > 代码库 > maxflow1273sap_gap
maxflow1273sap_gap
Sap和dinic复杂度一样的
优化：
1. 邻接表优化：如果顶点多，往往n^2存不下，这时候就要存边：存每条边的出发点，终点点和价值，然后排序一下，再记录每个出发点的位置。以后要调用从出发点出发的边时候，只需要从记录的位置开始找就可以（其实可以用链表）。优化是时间快空间节省，缺点是编程复杂度将变大，所以在题目允许的情况下，建议使用邻接矩阵。
2. GAP优化：如果一次重标号时，出现断层，则可以证明ST无可行流，此时则可以直接退出算法
3. 当前弧优化：为了使每次打增广路的时间变成均摊O(v)，还有一个重要的优化是对于每个点保存“当前弧”：初始时当前弧是邻接表的第一条弧；在邻接表中查找时从当前弧开始查找，找到了一条弧，就把这条弧设为当前弧；改变距离标号时，把当前弧设为邻接表的第一条弧。
GAP优化：如果一次重标号时，出现断层，则可以证明ST无可行流，此时则可以直接退出算法，。关于断流：
假设第四层节点只有一个z，说明无论有多少条增广路，最终一定要经过z点。那么当z不可使用的时候，必定不会再有增广路。
#include <cstdio>
#include <queue>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
struct Edge{
int cap, to;
int next;
}edge[N * 4];
int head[N], cnt, ans, des, src;
int gap[N], curedge[N], d[N], pre[N], que[N];
void bfs(){
memset(d, -1, sizeof(d));
memset(gap, 0, sizeof(gap));
gap[0] = 1;
int front = 0, rear = 0;
d[des] = 0;//从汇点开始
que[rear++] = des;
while(front != rear){
int deq = que[front++];
front = front % N;
for (int it = head[deq]; it != -1; it = edge[it].next)
{//head是邻接表形式，查看所有与dep相连的边，shortpath3159有关于邻接表的描述
int e = edge[it].to;
if (edge[it].cap != 0 || d[e] != -1)
continue;
que[rear++] = e;
rear = rear % N;
++gap[d[e] = d[deq] + 1];//gap[i]表示第i层的节点个数
}
}
}
struct ISAP{
// gap:统计高度数量数组；d:距离标号数组;
// curedges:当前弧数组;pre:前驱数组
void initi(){
fill(d + 1, d + n + 1, 0);
fill(pre + 1, pre + n + 1, -1);
fill(head + 1, head + n + 1, -1);
ans = 0; //初始化最大流为0
cnt = 0;
}
void addedge(int a, int b, int c){ //有向图加边。
edge[cnt].to = b, edge[cnt].cap = c;
edge[cnt].next = head[a], head[a] = cnt++;
edge[cnt].to = a, edge[cnt].cap = 0;
edge[cnt].next = head[b], head[b] = cnt++;
}
int max_flow(int start, int end){
int i, u, tmp, neck;
bfs();
for(i = 1;i <= n;i++)
curedge[i] = head[i]; //初始化当前弧为第一条邻接边
u = start;
while(d[start] < n){ //当d[start] >= n,网络中肯定出现了gap
if(u == end)
{ //增广成功，寻找瓶颈边
int min_flow = INT_MAX;
for(i = start;i != end;i = edge[curedge[i]].to){//直接从当前弧开始
if(min_flow > edge[curedge[i]].cap){
neck = i;
min_flow = edge[curedge[i]].cap;
}
}
for(i = start;i != end;i = edge[curedge[i]].to){//更新正反向弧流量
tmp = curedge[i];
edge[tmp].cap -= min_flow;
edge[tmp ^ 1].cap += min_flow;
//temp^1:
最低位异或
结果就是1变0,0变1,2变3，3变2。
就可以通过这样标记对应的反向边，也就是说，这里的邻接表中两个正、反向弧必须紧挨着存储了吧？也就是必须0，1是一组正反弧，2,3是一对，4,5是一对
}
ans += min_flow;
u = neck; //下次增广从瓶颈边开始
}
for(i = curedge[u];i != -1;i = edge[i].next)//从当前弧开始
if(edge[i].cap&&d[u] == d[edge[i].to] + 1)//寻找可行弧，u是起点，i是与u点直接相连或间接相连的各个边的序号,各个edge[i]的起点都是u
break;//通过当前弧，可以在以后的寻找增广路时，直接跳过不会用到的边（邻接表始终按照一种顺序存放），前面不会用的，后面也不会用。
//因为层级数在bfs确定后就不会被改变，所以层次关系如果第一次不满足以后永远不满足，另外如果是层次满足，但因为权值小于0，
if(i != -1)//那么将来不会变成正的，因为这意味着两次的增广路沿着两个节点换了一个方向，这显然不可能满足两个节点层级的关系，毕竟节点层级
{//永远不会被改变
curedge[u] = i;//改变u节点的当前弧，即与u节点直接相连的边是第i条边
pre[edge[i].to] = u;//记录路径
u = edge[i].to;//寻找下一层次节点
} else//U节点找不到下一个层级节点
{
if(--gap[d[u]] == 0)//断流
break;
curedge[u] = head[u];//从u节点周围选最小的，这里不是从当前弧开始，因为当前弧也没用。目的是在所有相连的边寻找
for(tmp = n, i = head[u];i != -1;i = edge[i].next)//同时当前弧也需要重新确定，所以赋值为第一个节点
if(edge[i].cap)
tmp = std::min(tmp, d[edge[i].to]);
d[u] = tmp + 1;
++gap[d[u]];
if(u != start)
u = pre[u]; //重标号并且从当前点前驱重新增广
}
}
return ans;
}
}g;
int main(){
int T;
cin >> T;
while(T--){
int i, a, b, c, sd = INT_MAX, dd = INT_MIN, x, y;
scanf("%d%d", &n, &m);
g.initi();
for(i = 1;i <= n;i++){
scanf("%d%d", &x, &y);
if(sd > x){
src = i;
sd = x;
}
if(dd < x){
des = i;
dd = x;
}
}
for(i = 0;i < m;i++){
scanf("%d%d%d", &a, &b, &c);
g.addedge(a, b, c);
g.addedge(b, a, c);
}
printf("%d\n", g.max_flow(src, des));
}
return 0;
}
maxflow1273sap_gap