【图论】网络流

网络流目前只整理模板，学习的话这篇博客可能不太适合

代码参考下方博客，加了一些自己的注释

• 算法学习笔记(28): 网络流
• 究级的最大流算法：ISAP与HLPP

FF 和 EK 仅用作理解代码，赛时请使用 Dinic 或 ISAP

下文建图方式都基于链式前向星，请注意，cnt 必须从 1 开始！！！！

void add(int u, int v, int val)
{cnt ++ ;node[cnt].to = v;node[cnt].w = val;node[cnt].next = head[u];head[u] = cnt;
}

Ford-Fulkerson (FF算法)

基于dfs的最大流算法

时间复杂度 $O(ef)$，e是边数，f是最大流

int n, m, start, end; // start是源点，end是汇点
bool st[MAXN]; // 标记某个点有没有被访问过struct edges
{int to, w, next;
};int dfs(int u, int flow) // u表示当前结点 flow表示目前流量
{if (p == t) return flow; // 到达终点，返回这条增广路的流量st[p] = true; // 标记已经访问过该点for (int eg = head[p]; eg != -1; eg = edges[eg].next) // 遍历所有邻接点{int to = edges[eg].to, w = edges[eg].w, c;if (w <= 0) continue; // 这条边不能再流过流量if (st[to]) continue; // 已经经过该点c = dfs(to, min(w, flow)); // 递归判断接下来能否到达终点 传递下去的流量是边的容量w与当前流量flow中的较小值if (c != -1) // 可以到达终点{edges[eg].w -= c; // 正向边容量w减去流量cedges[eg ^ 1].w += c; // 反向边容量w加上流量c// 建图时要把cnt置为1，且要保证反向边紧接着正向边建立return c; // 返回值是流量}}return -1; // 无法到达终点
}int FF()
{int ans = 0, c; // ans代表总流量while ((c = dfs(start, INF)) != -1) // 只要还可以到达终点就一直dfs下去{memset(st, 0, sizeof(st)); // 初始化每个点的访问状态ans += c; // 加上本次dfs的流量}return ans;
}

Edmond-Karp (EK算法)

基于bfs的最大流算法

时间复杂度 $O(v{e}^2)$，v是点数，e是边数

// last表示该条增广路中通向该点的边的编号 flow表示每个点可以流过的最大流量（也就是从上一个点传过来的流量）
int n, m, start, end, last[MAXN], flow[MAXN]; struct edges
{int to, w, next;
};int bfs()
{memset(last, -1, sizeof(last)); // 初始化每个点的增广路径queue<int> q;q.push(start);flow[start] = INF; // 源点可以流过的流量初始化为无穷大while (!q.empty()){int u = q.front();q.pop();if (u == t) break; // 到达汇点，结束搜索for (int eg = head[u]; eg != -1; eg = edges[eg].next) // 遍历所有邻接点{int to = edges[eg].to, w = edges[eg].w;if (w > 0 && last[to] == -1) // 如果残余容量大于0且未访问过（所以last保持在-1）{last[to] = eg; // 记录点to在本条增广路的上一条边的编号是egflow[to] = min(flow[p], w); // 取边的容量和上一个点可以流过的流量的最小值q.push(to); // 新点入队}}}return last[end] != -1; // 如果汇点没有访问到，说明没有可以通向汇点的路了
}int EK()
{int maxflow = 0; // maxflow代表总流量while (bfs()) // 只要还可以到达终点就一直bfs下去{maxflow += flow[end]; // 更新总流量 也就是加上能流到汇点的流量for (int i = end; i != start; i = edges[last[i] ^ 1].to) // 从汇点原路返回更新残余容量{edges[last[i]].w -= flow[end]; // 正向边容量w减去该条增广路流量flow[end]edges[last[i] ^ 1].w += flow[end]; // 反向边容量w加上该条增广路流量flow[end]}}return maxflow;
}

Dinic算法

基于FF和EK的最大流算法

时间复杂度$O(n^{2}e)$，n是点数，e是边数

先使用bfs分层，再使用dfs搜索，每次只往层数高的地方走，可以避免走重复的路径

优化：

• 多路增广：在某点找到一条增广路，如果流量没用完，就接着往下bfs
• 当前弧优化：在Dinic中每条边只会增广一次，所以下次增广就不需要考虑已经增广过的边，通过修改起始结点可以实现这个优化

注意：Dinic用在二分图中复杂度是 $O(v\sqrt{e})$，v是点数，e是边数 ，优于匈牙利算法。

int n, m, start, end, dep[MAXN], cur[MAXN]; // dep是每个点的层数 cur用于当前弧优化标记增广起点struct edges
{int to, w, next;
};bool bfs() // BFS分层
{memset(dep, -1, sizeof(dep)); // 初始化点的层数dep[start] = 0; // 初始化源点的层数为0memcpy(cur, head, sizeof(head)); // 当前弧优化初始化queue<int> q;q.push(start); // 源点入队while (!q.empty()){int u = q.front();q.pop();for (int eg = head[u]; eg; eg = edges[eg].next) // 遍历所有邻接点{int to = edges[eg].to, w = edges[eg].w;if (w > 0 && dep[to] == -1) // dep为-1说明没访问过{dep[to] = dep[u] + 1; // 更新to点层数q.push(to);}}}return dep[end] != -1; // 如果汇点未访问过说明已经无法达到汇点，此时返回false
}int dfs(int u, int flow) // u表示当前结点 flow表示目前流量
{if (u == end) return flow; // 找到汇点 返回目前的流量int rmn = flow; // rmn表示剩余的流量for (int eg = cur[u]; eg != -1; eg = edges[eg].next) // 遍历所有邻接点{if (rmm == 0) break; // 无余量直接退出cur[u] = eg; // 当前弧优化 更新当下次访问该点时从哪条边开始遍历int to = edges[eg].to, w = edges[eg].w;if (w > 0 && dep[to] == dep[u] + 1) // 往层数高的方向增广{int c = dfs(to, min(w, rmn)); // 递归得到该点流量 传递下去的流量是边的容量w与当前流量flow中的较小值rmn -= c; // 剩余流量减少edges[eg].w -= c; // 正向边容量w减去流量cedges[eg ^ 1].w += c; // 反向边容量w加上流量c}}return flow - rmn; // 返回传递的流量的大小
}int dinic()
{int ans = 0; // ans代表总流量while (bfs()) // 只要还可以到达终点就一直bfs下去ans += dfs(start, INF);return ans;
}

Improved Shortest Augumenting Path (ISAP算法)

考虑到Dinic中可能需要bfs多次，ISAP对此做出改进，只需要进行一次bfs即可

首先跑一遍bfs，从汇点到源点处理每个结点的深度

再从源点到汇点跑dfs，和Dinic类似，只是当一个点跑完后，如果从上一个点传过来的流量 flow 比该点的流过的流量 used 大，说明这个点的使用价值已经榨干了，但是还有剩余的流量，则把它的深度加1，如果出现断层（某个深度没有点），结束算法，没出现就一直跑下去

下方代码已加入当前弧优化

struct Edge
{int to, next, w;
};int dep[maxn], gap[maxn]; // dep[i]表示结点i在第几层 gap[i]表示第i层有多少结点
void bfs()
{memset(dep, -1, sizeof(dep));memset(gap, 0, sizeof(gap));dep[end] = 0; // 汇点层数初始化为0gap[0] = 1; // 层数为0的点个数初始化为1queue<int> q;q.push(end); // 汇点入队while (!q.empty()){int u = q.front();q.pop();for (int i = head[u]; i != -1; i = edge[i].next){int to = edge[i].to;if (dep[to] != -1) continue; // 层数不为-1说明已经访问过这个点了dep[to] = dep[u] + 1; // 更新to点层数gap[dep[to]] ++ ; // 更新该层数点的数量 q.push(to); // to点入队}}return;
}int maxflow;
int dfs(int u, int flow) // u表示当前结点 flow表示目前流量
{if (u == end) // 找到汇点{maxflow += flow; // 更新最大流量return flow; // 返回目前的流量}int used = 0; // 从u开始使用的流量for (int i = cur[u]; i != -1; i = edge[i].next){cur[u] = i; // 当前弧优化 更新当下次访问该点时从哪条边开始遍历int to = edge[i].to, w = edge[i].w;if (w > 0 && dep[to] + 1 == dep[u]) // 边还有余量and层数符合要求（注意计算层数的时候是从汇点到源点的）{int c = dfs(to, min(w, flow - used)); // 递归得到该点流量 传递下去的流量是边的容量w与当前流量flow-used中的较小值if (c > 0){edge[i].w -= c; // 正向边容量w减去流量cedge[i ^ 1].w += c; // 反向边容量w加上流量cused += c; // 更新已经用过的流量}if (used == flow) return used; // used和flow相等说明已经没有剩余流量分给其他的边了 所以直接返回}}// 如果能到这一步 说明u的所有邻接点都已经遍历过了 且还有剩余流量// 此时我们需要修改u点的层数gap[dep[u]] -- ; // 修改原本层数的结点数if (gap[dep[u]] == 0) dep[start] = n + 1; // 说明没有层数为dep[u]的结点了 断层 不可能再到达汇点了dep[u] ++ ; // 更新u的层数gap[dep[u]] ++ ; // 更新新层数的结点数return used; // 返回流过的流量
}int ISAP()
{maxflow = 0; // maxflow是最大流量bfs();while (dep[start] < n){memcpy(cur, head, sizeof(head));dfs(s, INF);}return maxflow;
}