【图论】网络流
网络流目前只整理模板，学习的话这篇博客可能不太适合
代码参考下方博客，加了一些自己的注释
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
(
e
f
)
O(ef)
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减去流量c
edges[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
)
O(ve^2)
O(ve2)，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在本条增广路的上一条边的编号是eg
flow[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
)
O(n^2e)
O(n2e)，n是点数，e是边数
先使用bfs分层，再使用dfs搜索，每次只往层数高的地方走，可以避免走重复的路径
优化：
- 多路增广：在某点找到一条增广路，如果流量没用完，就接着往下bfs
- 当前弧优化：在Dinic中每条边只会增广一次，所以下次增广就不需要考虑已经增广过的边，通过修改起始结点可以实现这个优化
注意：Dinic用在二分图中复杂度是
O
(
v
e
)
O(vsqrt{e})
O(ve
)，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; // 初始化源点的层数为0
memcpy(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减去流量c
edges[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; // 汇点层数初始化为0
gap[0] = 1; // 层数为0的点个数初始化为1
queue<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减去流量c
edge[i ^ 1].w += c; // 反向边容量w加上流量c
used += 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;
}