当前位置： 首页 > article >正文

16 网络流

article 2024/12/26 7:32:28

图论 —— 网络流_图论中网络流的定义-CSDN博客

算法学习笔记(28): 网络流 - 知乎 (zhihu.com)

语雀版本

1 概念

例子：1为源点，3为汇点

2 最大流

**最大流问题**是指，在一个流网络中，找到一种流量分配，使得从源点 sss 到汇点 ttt 的总流量达到最大，并满足每条边的容量限制。

2.1 Ford-Fulkerson算法

**思路：**利用dfs查找增广路，直到找不到为止。（先不考虑反向边）

增广路：源点到汇点的路径，且路径中所有边的残余容量均大于零。

例子解读：

**dfs找到第一条：**1->2->3，其中的容量最小的边是2->3，所以，这条增广路的流量为2。相应地扣除掉流量，使得1->2的残余容量为1,2->4为3,4->3为2,2->3为0。

dfs查找第二条：1->2->4->3，流量为1。更新残余容量。

第三条：1->3，流量为2。更新残余容量。

找不到了，终止。计算总流量。

上述方法可能会有个问题，如下图，如果我第一次搜索是1->2->3->4，则没法找到新的增广路了，流量为1。但实际上可以1->3->4,1->2->4两条增广路，流量为2。

Ford-Fulkerson算法（考虑反向边）： 在扣除正向边的容量时，反向边要加上等量的容量。

**目的：**一个节点的容量是可以撤回的，比如某条路径需要它从一边流到另一边，另一条路需要它从另一边流到这一边。这是可以抵消的。这就可以避免上面例子出现的问题。

找到1->2->3->4，然后扣容量，加到反向边上。

上图可以找到第二条增广路：1->3->2->4

上图无法再找到，终止。

#include <iostream>
#include <cstdio>
#include <cstring> // 使用 memset
#include <stack>
#include <algorithm> // 使用 min

using namespace std;

const int MAXN = 5005; // 最大的节点数
const int MAXM = 10005; // 最大的边数（正向边 + 反向边）
const int INF = 1e9; // 无穷大，表示极大容量

struct Edge {
    int to;   // 边的目标节点
    int w;    // 边的容量
    int next; // 链式前向星中的下一条边
};

Edge edges[MAXM * 2]; // 存储边的数组，正向边和反向边都要存
int head[MAXN], tot = 0; // head[] 是链式前向星中每个节点的第一条边，tot 是边的总数
int n, m, s, t; // n 是节点数，m 是边数，s 是源点，t 是汇点
bool vis[MAXN]; // 访问标记数组，防止DFS中重复访问节点

// 添加一条边 u -> v，容量为 w，同时添加反向边 v -> u，容量为 0
void add_edge(int u, int v, int w) {
    edges[tot] = {v, w, head[u]}; // 正向边 u -> v
    head[u] = tot++;
    edges[tot] = {u, 0, head[v]}; // 反向边 v -> u，容量为0
    head[v] = tot++;
}

// 深度优先搜索寻找增广路径，p 是当前节点，flow 是当前路径上的最小残余流量
int dfs(int p = s, int flow = INF) {
    if (p == t)
        return flow; // 到达汇点，返回当前路径上的流量
    vis[p] = true; // 标记当前节点已访问，防止重复访问
    for (int eg = head[p]; eg != -1; eg = edges[eg].next) {
        int to = edges[eg].to, vol = edges[eg].w, c;
        // 递归条件：残余容量大于0，且目标节点未被访问
        if (vol > 0 && !vis[to] && (c = dfs(to, min(vol, flow))) != -1) {
            edges[eg].w -= c;        // 正向边容量减少
            edges[eg ^ 1].w += c;    // 反向边容量增加，eg ^ 1 是反向边  正向边编号都是偶数，与1按位异或，即+1
            return c;                // 返回增广路径上的流量
        }
    }
    return -1; // 无法找到增广路径，返回 -1
}

// Ford-Fulkerson 主函数，计算从源点到汇点的最大流
int FF() {
    int ans = 0, c;
    while ((c = dfs()) != -1) { // 不断寻找增广路径
        memset(vis, 0, sizeof(vis)); // 每次DFS后重置访问标记数组
        ans += c; // 累加找到的增广路径流量
    }
    return ans; // 返回最大流
}

int main() {
    cin >> n >> m >> s >> t; // 输入节点数、边数、源点、汇点
    memset(head, -1, sizeof(head)); // 初始化链式前向星的 head 数组为 -1

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 输入每条边的起点 u、终点 v 和容量 w
        add_edge(u, v, w);  // 添加这条边（包括反向边）
    }

    int max_flow = FF(); // 调用 Ford-Fulkerson 算法求解最大流
    cout << "The maximum flow is: " << max_flow << endl;

    return 0;
}

用dfs实现的FF算法时间复杂度上界是 O(ef) ，其中 e 为边数，f 为最大流

2.2 Edmonds-Karp算法

DFS很可能会“绕远路”，而BFS可以保证每次找到的都是最短的增广路。它的复杂度上限是 O(ve^2) ，其中 v 为点数，e为边数。 
#include <iostream>
#include <cstdio>
#include <cstring> // 使用 memset
#include <queue>   // 使用 BFS 队列
#include <algorithm> // 使用 min

using namespace std;

const int MAXN = 5005;  // 最大的节点数
const int MAXM = 10005; // 最大的边数（正向边 + 反向边）
const int INF = 1e9;    // 无穷大，表示极大容量

struct Edge {
    int to;   // 边的目标节点
    int w;    // 边的容量
    int next; // 链式前向星中的下一条边
};

Edge edges[MAXM * 2]; // 存储边的数组，正向边和反向边都要存
int head[MAXN], tot = 0; // head[] 是链式前向星中每个节点的第一条边，tot 是边的总数
int n, m, s, t;          // n 是节点数，m 是边数，s 是源点，t 是汇点
int last[MAXN], flow[MAXN]; // last[] 记录每个节点到达的边，flow[] 记录增广路径上的流量

// 添加一条边 u -> v，容量为 w，同时添加反向边 v -> u，容量为 0
void add_edge(int u, int v, int w) {
    edges[tot] = {v, w, head[u]}; // 正向边 u -> v
    head[u] = tot++;
    edges[tot] = {u, 0, head[v]}; // 反向边 v -> u，容量为 0
    head[v] = tot++;
}

// 广度优先搜索寻找增广路径，返回是否能找到从源点 s 到汇点 t 的路径
inline int bfs() {
    memset(last, -1, sizeof(last)); // 初始化 last 数组为 -1，表示每个点未访问过
    queue<int> q;  // BFS 队列
    q.push(s);     // 从源点 s 开始
    flow[s] = INF; // 源点的初始流量为无穷大，表示可以从这里开始尽量多流量传输
    
    while (!q.empty()) { // BFS 遍历
        int p = q.front();
        q.pop();

        if (p == t) // 一旦到达汇点 t，结束 BFS 搜索
            break;

        for (int eg = head[p]; eg != -1; eg = edges[eg].next) { // 遍历 p 节点的所有邻接边
            int to = edges[eg].to, vol = edges[eg].w;
            
            // 条件：边的剩余容量 vol > 0 且目标节点未被访问过（last[to] == -1）
            if (vol > 0 && last[to] == -1) {
                last[to] = eg; // 记录到达 to 节点的边
                flow[to] = min(flow[p], vol); // 更新到达 to 节点的最大流量
                q.push(to); // 将 to 节点加入队列，继续向下层搜索
            }
        }
    }
    
    return last[t] != -1; // 是否找到增广路径，若 last[t] != -1 表示找到增广路径
}

// Edmond-Karp 主函数，计算最大流
inline int EK() {
    int maxflow = 0; // 初始化最大流为 0
    
    // 不断通过 BFS 寻找增广路径
    while (bfs()) {
        maxflow += flow[t]; // 增加这条增广路径的流量到最大流
        
        // 从汇点 t 沿着增广路径逆向更新每条边的残余容量
        for (int i = t; i != s; i = edges[last[i] ^ 1].to) {
            edges[last[i]].w -= flow[t];        // 正向边容量减少
            edges[last[i] ^ 1].w += flow[t];    // 反向边容量增加
        }
    }
    
    return maxflow; // 返回计算得到的最大流
}

int main() {
    cin >> n >> m >> s >> t; // 输入节点数、边数、源点、汇点
    memset(head, -1, sizeof(head)); // 初始化链式前向星的 head 数组为 -1
    
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 输入每条边的起点 u、终点 v 和容量 w
        add_edge(u, v, w);  // 添加这条边（包括反向边）
    }

    int max_flow = EK(); // 调用 Edmond-Karp 算法求解最大流
    cout << "The maximum flow is: " << max_flow << endl;

    return 0;
}

2.3 Dinic算法

Dinic算法（也称为Dinitz算法）是解决**最大流问题**的常用高效算法。与 **Ford-Fulkerson** 和 **Edmonds-Karp** 不同，Dinic算法通过分层图的概念结合了 **广度优先搜索（BFS）** 和 **深度优先搜索（DFS）**，从而提高了在残余网络中寻找增广路径的效率。

Dinic算法的核心思想：

  1. 分层图：通过广度优先搜索（BFS）对网络进行分层，分层图中的每一层表示从源点出发到达各个节点的最短距离（层数）。分层的目的是确保增广流量时，始终向层数更高的节点推进，避免“走回头路”。
  2. DFS多路增广：在分层图的基础上，通过深度优先搜索（DFS）寻找尽可能多的增广路径，并且在一次DFS中，尽可能多地传递流量。
  3. 当前弧优化：利用当前弧优化减少不必要的重复路径探索。在某条边已经增广过一次后，未来的增广不再考虑这条边，进一步提高算法效率。

Dinic算法的流程：

  1. BFS构建分层图：从源点开始，使用广度优先搜索给每个节点赋予层数。层数表示从源点到达该节点的最短路径长度。
  2. DFS增广路径：在分层图上，通过深度优先搜索，沿着从层数低到层数高的方向寻找增广路径，并尽可能多地传递流量。
  3. 循环执行步骤1和2，直到无法再找到增广路径为止。

**时间复杂度：**O(V^2E)

当前弧优化： 在当前弧优化中，通常使用一个数组 cur[] 来记录 DFS 在每个节点处当前处理的边。每次 DFS 增广时，优先从 cur[p] 记录的边开始搜索，而不是重新从该节点的第一条边开始。

#include <iostream>
#include <cstring> // 使用 memset 和 memcpy
#include <queue>   // 使用 BFS 的队列
#include <algorithm> // 使用 min

using namespace std;

const int MAXN = 5005;  // 最大的节点数
const int MAXM = 10005; // 最大的边数（正向边 + 反向边）
const int INF = 1e9;    // 无穷大，表示极大容量

struct Edge {
    int to;   // 边的目标节点
    int w;    // 边的容量
    int next; // 链式前向星中的下一条边
};

Edge edges[MAXM * 2]; // 存储边的数组，正向边和反向边都要存
int head[MAXN], tot = 0; // head[] 是链式前向星中每个节点的第一条边，tot 是边的总数
int n, m, s, t;          // n 是节点数，m 是边数，s 是源点，t 是汇点
int lv[MAXN], cur[MAXN];  // lv[] 是每个节点的层数，cur[] 用于当前弧优化标记增广起点

// 添加一条边 u -> v，容量为 w，同时添加反向边 v -> u，容量为 0
void add_edge(int u, int v, int w) {
    edges[tot] = {v, w, head[u]}; // 正向边 u -> v
    head[u] = tot++;
    edges[tot] = {u, 0, head[v]}; // 反向边 v -> u，容量为 0
    head[v] = tot++;
}

// BFS 构建分层图，判断是否还能找到增广路径
inline bool bfs() {
    memset(lv, -1, sizeof(lv)); // 初始化层数 lv[] 为 -1，表示未访问
    lv[s] = 0; // 源点的层数为 0
    memcpy(cur, head, sizeof(head)); // 当前弧优化初始化，复制 head 数组
    queue<int> q; // BFS 队列
    q.push(s);    // 将源点入队列
    
    // 通过 BFS 构建分层图
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        
        for (int eg = head[p]; eg != -1; eg = edges[eg].next) {
            int to = edges[eg].to, vol = edges[eg].w;
            
            // 若该边有剩余容量且目标节点未访问过
            if (vol > 0 && lv[to] == -1) {
                lv[to] = lv[p] + 1; // 更新目标节点的层数
                q.push(to); // 将目标节点入队列
            }
        }
    }
    
    return lv[t] != -1; // 判断汇点是否被访问过，若未访问过则无法找到增广路径
}

// DFS 多路增广，寻找增广路径并传递流量
int dfs(int p, int flow) {
    if (p == t) // 若到达汇点，则返回这条路径上的流量
        return flow;
    
    int rmn = flow; // 剩余的流量
    for (int eg = cur[p]; eg != -1 && rmn > 0; eg = edges[eg].next) {
        cur[p] = eg; // 当前弧优化，更新当前弧
        int to = edges[eg].to, vol = edges[eg].w;
        
        // 只往层数更高的节点增广
        if (vol > 0 && lv[to] == lv[p] + 1) {
            int c = dfs(to, min(vol, rmn)); // 递归传递流量
            if (c > 0) { // 如果成功增广
                rmn -= c; // 剩余流量减少
                edges[eg].w -= c; // 更新正向边的容量
                edges[eg ^ 1].w += c; // 更新反向边的容量
            }
        }
    }
    
    return flow - rmn; // 返回实际传递出去的流量
}

// Dinic 算法的主函数，计算最大流
inline int dinic() {
    int maxflow = 0; // 初始化最大流为 0
    
    // 不断通过 BFS 构建分层图，然后通过 DFS 增广
    while (bfs()) {
        maxflow += dfs(s, INF); // 累加每次增广的流量
    }
    
    return maxflow; // 返回最大流
}

int main() {
    cin >> n >> m >> s >> t; // 输入节点数、边数、源点和汇点
    memset(head, -1, sizeof(head)); // 初始化链式前向星的 head 数组为 -1
    
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 输入每条边的起点 u、终点 v 和容量 w
        add_edge(u, v, w);  // 添加这条边（包括反向边）
    }

    int max_flow = dinic(); // 调用 Dinic 算法求解最大流
    cout << "The maximum flow is: " << max_flow << endl;

    return 0;
}

2.4 最大流最小割定理

**定理：**一个流网络中，从源点到汇点的最大流量，等于从源点到汇点的最小割的容量。

最小割问题是指，将图中的节点分为两个部分，使源点 sss 和汇点 ttt 分别位于不同的部分，割断所有从源点部分到汇点部分的边，且这些被割断边的总容量最小。这些割断的边就是“最小割”。

割的定义：

  • 割是指在流网络中，找到一组边的集合，这些边的删除将使得源点 s 和汇点 t不再连通。
  • 割的容量：割的容量是被切断边的总容量之和。

3 最大流最小割

+ **最大流**：使用 **Dinic算法** 求出从源点 sss 到汇点 ttt 的最大流。 + **查找最小割的节点集**：使用 **DFS** 或 **BFS** 从源点 sss 开始，找到残余网络中能到达的所有节点，这些节点形成一个集合 SSS。 + **确定最小割边**：遍历所有边，如果一条边的起点在集合 SSS 中，而终点在集合 TTT（即不在 SSS 中），这条边就是最小割的一部分。 
#include <iostream>
#include <cstring> // 使用 memset 和 memcpy
#include <queue>   // 使用 BFS 的队列
#include <algorithm> // 使用 min

using namespace std;

const int MAXN = 5005;  // 最大的节点数
const int MAXM = 10005; // 最大的边数（正向边 + 反向边）
const int INF = 1e9;    // 无穷大，表示极大容量

struct Edge {
    int to;   // 边的目标节点
    int w;    // 边的容量
    int next; // 链式前向星中的下一条边
};

Edge edges[MAXM * 2]; // 存储边的数组，正向边和反向边都要存
int head[MAXN], tot = 0; // head[] 是链式前向星中每个节点的第一条边，tot 是边的总数
int n, m, s, t;          // n 是节点数，m 是边数，s 是源点，t 是汇点
int lv[MAXN], cur[MAXN];  // lv[] 是每个节点的层数，cur[] 用于当前弧优化标记增广起点
bool visited[MAXN];       // 用于记录从源点可达的节点

// 添加一条边 u -> v，容量为 w，同时添加反向边 v -> u，容量为 0
void add_edge(int u, int v, int w) {
    edges[tot] = {v, w, head[u]}; // 正向边 u -> v
    head[u] = tot++;
    edges[tot] = {u, 0, head[v]}; // 反向边 v -> u，容量为 0
    head[v] = tot++;
}

// BFS 构建分层图，判断是否还能找到增广路径
inline bool bfs() {
    memset(lv, -1, sizeof(lv)); // 初始化层数 lv[] 为 -1，表示未访问
    lv[s] = 0; // 源点的层数为 0
    memcpy(cur, head, sizeof(head)); // 当前弧优化初始化，复制 head 数组
    queue<int> q; // BFS 队列
    q.push(s);    // 将源点入队列
    
    // 通过 BFS 构建分层图
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        
        for (int eg = head[p]; eg != -1; eg = edges[eg].next) {
            int to = edges[eg].to, vol = edges[eg].w;
            
            // 若该边有剩余容量且目标节点未访问过
            if (vol > 0 && lv[to] == -1) {
                lv[to] = lv[p] + 1; // 更新目标节点的层数
                q.push(to); // 将目标节点入队列
            }
        }
    }
    
    return lv[t] != -1; // 判断汇点是否被访问过，若未访问过则无法找到增广路径
}

// DFS 多路增广，寻找增广路径并传递流量
int dfs(int p, int flow) {
    if (p == t) // 若到达汇点，则返回这条路径上的流量
        return flow;
    
    int rmn = flow; // 剩余的流量
    for (int eg = cur[p]; eg != -1 && rmn > 0; eg = edges[eg].next) {
        cur[p] = eg; // 当前弧优化，更新当前弧
        int to = edges[eg].to, vol = edges[eg].w;
        
        // 只往层数更高的节点增广
        if (vol > 0 && lv[to] == lv[p] + 1) {
            int c = dfs(to, min(vol, rmn)); // 递归传递流量
            if (c > 0) { // 如果成功增广
                rmn -= c; // 剩余流量减少
                edges[eg].w -= c; // 更新正向边的容量
                edges[eg ^ 1].w += c; // 更新反向边的容量
            }
        }
    }
    
    return flow - rmn; // 返回实际传递出去的流量
}

// Dinic 算法的主函数，计算最大流
inline int dinic() {
    int maxflow = 0; // 初始化最大流为 0
    
    // 不断通过 BFS 构建分层图，然后通过 DFS 增广
    while (bfs()) {
        maxflow += dfs(s, INF); // 累加每次增广的流量
    }
    
    return maxflow; // 返回最大流
}

// DFS 查找从源点可以到达的节点，用于构建最小割
void find_min_cut(int node) {
    visited[node] = true;
    for (int eg = head[node]; eg != -1; eg = edges[eg].next) {
        int to = edges[eg].to, vol = edges[eg].w;
        if (vol > 0 && !visited[to]) { // 只遍历残余容量大于0的边
            find_min_cut(to); // 递归找到所有可以从源点到达的节点
        }
    }
}

int main() {
    cin >> n >> m >> s >> t; // 输入节点数、边数、源点和汇点
    memset(head, -1, sizeof(head)); // 初始化链式前向星的 head 数组为 -1
    
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 输入每条边的起点 u、终点 v 和容量 w
        add_edge(u, v, w);  // 添加这条边（包括反向边）
    }

    int max_flow = dinic(); // 调用 Dinic 算法求解最大流
    cout << "The maximum flow is: " << max_flow << endl;

    // 寻找从源点可以到达的所有节点
    memset(visited, false, sizeof(visited));
    find_min_cut(s);

    // 输出最小割中的边
    cout << "The edges in the minimum cut are: " << endl;
    for (int i = 0; i < tot; i += 2) { // 遍历所有正向边
        int u = edges[i ^ 1].to; // 正向边的起点
        int v = edges[i].to;     // 正向边的终点
        if (visited[u] && !visited[v]) { // 如果u可达，而v不可达，说明这条边属于最小割
            cout << u << " -> " << v << " (capacity: " << edges[i].w + edges[i ^ 1].w << ")" << endl;
        }
    }

    return 0;
}

4 最小费用最大流

网络上的每条边，除了容量外，** 还有一个属性：单位费用** 。一条边上的费用等于流量×单位费用。我们知道，网络最大流往往可以用多种不同的方式达到，所以现在要求：** 在保持流最大的同时，找到总费用最少的一种。**

常用的方法：MCMF费用流（将EK算法中的bfs改为SPFA）；改进的Dijkstra算法（听说比较费时，不实用）；ZKW费用流（最高效，将Dinic算法中的bfs改为SPFA）

4.1 MCMF-基于EK和SPFA

+ **EK** 使用的是基于 **BFS** 的增广路径，每次找到的是**边数最少**的路径，然后立即增广。 + **SPFA** 则是通过动态更新路径费用来寻找**费用最小**的路径，并不是寻找边数最少的路径。 
#include <iostream>
#include <cstdio>
#include <cstring> // 使用 memset
#include <queue>   // 使用 SPFA 队列
#include <algorithm> // 使用 min
#include <vector>

using namespace std;

const int MAXN = 5005;  // 最大的节点数
const int MAXM = 10005; // 最大的边数（正向边 + 反向边）
const int INF = 1e9;    // 无穷大，表示极大容量

struct Edge {
    int to;   // 边的目标节点
    int cap;  // 边的容量
    int cost; // 边的费用
    int next; // 链式前向星中的下一条边
};

Edge edges[MAXM * 2]; // 存储边的数组，正向边和反向边都要存
int head[MAXN], tot = 0; // head[] 是链式前向星中每个节点的第一条边，tot 是边的总数
int n, m, s, t;          // n 是节点数，m 是边数，s 是源点，t 是汇点
int last[MAXN], flow[MAXN], dist[MAXN];  // last[] 记录每个节点到达的边，flow[] 记录增广路径上的流量, dist[] 记录最短路径距离
bool in_queue[MAXN]; // 标记每个点是否在队列中
int total_cost = 0;  // 总费用

// 添加一条边 u -> v，容量为 cap，费用为 cost，同时添加反向边
void add_edge(int u, int v, int cap, int cost) {
    edges[tot] = {v, cap, cost, head[u]}; // 正向边
    head[u] = tot++;
    edges[tot] = {u, 0, -cost, head[v]}; // 反向边，容量为 0，费用为相反数
    head[v] = tot++;
}

// SPFA 寻找从源点 s 到汇点 t 的最短费用路径
bool spfa() {
    memset(dist, INF, sizeof(dist)); // 初始化最短路径距离为无穷大
    memset(in_queue, false, sizeof(in_queue));
    memset(last, -1, sizeof(last));  // 初始化 last 数组

    queue<int> q;
    q.push(s);
    dist[s] = 0;
    flow[s] = INF;
    in_queue[s] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (int eg = head[u]; eg != -1; eg = edges[eg].next) {
            int v = edges[eg].to;
            int cap = edges[eg].cap;
            int cost = edges[eg].cost;

            // 如果该边还有剩余容量，并且通过这条边能找到更短的路径
            if (cap > 0 && dist[v] > dist[u] + cost) {
                dist[v] = dist[u] + cost;
                last[v] = eg; // 记录到达 v 的边
                flow[v] = min(flow[u], cap); // 更新增广流量

                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }

    return dist[t] != INF; // 如果到达汇点 t，返回 true
}

// 最小费用最大流的主函数
pair<int, int> min_cost_max_flow() {
    int max_flow = 0;
    total_cost = 0;

    while (spfa()) { // 不断寻找最短费用增广路径
        max_flow += flow[t]; // 增加流量
        total_cost += flow[t] * dist[t]; // 增加费用

        // 更新路径上的容量
        for (int v = t; v != s; v = edges[last[v] ^ 1].to) {
            edges[last[v]].cap -= flow[t]; // 正向边减少流量
            edges[last[v] ^ 1].cap += flow[t]; // 反向边增加流量
        }
    }

    return {max_flow, total_cost}; // 返回最大流和总费用
}

int main() {
    cin >> n >> m >> s >> t; // 输入节点数、边数、源点和汇点
    memset(head, -1, sizeof(head)); // 初始化链式前向星的 head 数组为 -1
    
    for (int i = 0; i < m; ++i) {
        int u, v, cap, cost;
        cin >> u >> v >> cap >> cost; // 输入每条边的起点 u、终点 v、容量和费用
        add_edge(u, v, cap, cost);  // 添加边
    }

    pair<int, int> result = min_cost_max_flow(); // 调用最小费用最大流函数
    cout << "Maximum Flow: " << result.first << endl;
    cout << "Minimum Cost: " << result.second << endl;

    return 0;
}

4.2 ZKW-基于Dinic和SPFA

MCMF每次bfs后，只有一条增广路，有点浪费时间。

ZKW利用Dinic算法来实现，可以每次分层后，尽可能地把流量分配下去，即可以找到尽可能多的增广路。

  • SPFA（Shortest Path Faster Algorithm）分层：
  • 通过 SPFA 为图中的每个节点计算到源点的最短路径，同时为节点分层。层数用于在增广路径时约束方向：从层数较低的节点流向层数较高的节点。
  • SPFA 保证每次增广的路径费用最小。
  • DFS增广：
  • 在分层图上使用 DFS 增广流量。DFS 遍历层次，尽可能多地传递流量。
  • 当找到从源点到汇点的一条可行路径时，沿路径增广流量并更新边的容量和费用。
  • ZKW循环增广：
  • 每次通过 SPFA 分层后，使用 DFS 增广流量。如果本次 SPFA 之后不能再增广，则算法终止。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
#include <algorithm>

using namespace std;

const int INF = 1e9;       // 无穷大，表示极大容量
const int MAXN = 505;      // 最大的节点数
const int MAXM = 50005;    // 最大的边数（正向边 + 反向边）

// 定义边结构体
struct Edge {
    int to;     // 边的目标节点
    int next;   // 链式前向星中的下一条边
    int cap;    // 边的容量
    int cost;   // 边的费用
} edge[MAXM];

int head[MAXN], tot;  // head[] 记录每个节点的第一条边的索引，tot 是边的总数
bool vis[MAXN];       // 访问标记数组，用于 SPFA 算法
int dis[MAXN];        // 存储从源点到每个节点的最短路径距离
int level[MAXN];      // 记录每个节点的层数（用于分层）
int n, m;             // n 为节点数，m 为边数

// 添加一条容量为 cap，费用为 cost 的边 u -> v，同时添加反向边 v -> u
void addEdge(int u, int v, int cap, int cost) {
    edge[++tot] = {v, head[u], cap, cost};  // 正向边
    head[u] = tot;
    
    edge[++tot] = {u, head[v], 0, -cost};  // 反向边，容量为 0，费用为相反数
    head[v] = tot;
}

// SPFA 算法，用于为图中的节点分层并寻找最短费用路径
bool SPFA(int S, int T) {
    memset(dis, INF, sizeof(dis));  // 初始化最短路径距离为无穷大
    memset(vis, false, sizeof(vis)); // 初始化访问数组
    memset(level, 0, sizeof(level)); // 初始化层数数组
    dis[S] = 0;
    level[S] = 1;
    vis[S] = true;

    deque<int> Q;
    Q.push_back(S);  // 将源点加入队列

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop_front();
        vis[u] = false;

        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (edge[i].cap > 0 && dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost; // 更新最短路径
                level[v] = level[u] + 1;  // 更新层次
                if (!vis[v]) {
                    vis[v] = true;
                    // 优化队列操作，SLF 优化
                    if (!Q.empty() && dis[v] < dis[Q.front()]) 
                        Q.push_front(v);
                    else
                        Q.push_back(v);
                }
            }
        }
    }
    return dis[T] != INF;  // 返回是否存在可行路径
}

bool flag;  // 增广标志，用于判断是否找到可增广路径

// DFS 增广函数，尝试在分层图中找到增广路径
int dfs(int u, int T, int flow, int &total_flow, int &total_cost) {
    if (u == T) {  // 如果到达汇点
        total_flow += flow;  // 增加总流量
        flag = true;
        return flow;  // 返回增广的流量
    }
    int used_flow = 0, new_flow;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        // 判断是否可以增广：1. 路径的费用符合条件，2. 层次符合条件，3. 有剩余容量
        if (edge[i].cap > 0 && dis[u] + edge[i].cost == dis[v] && level[u] + 1 == level[v]) {
            new_flow = dfs(v, T, min(flow - used_flow, edge[i].cap), total_flow, total_cost);
            used_flow += new_flow;  // 更新已经增广的流量
            total_cost += new_flow * edge[i].cost;  // 增加总费用
            edge[i].cap -= new_flow;  // 更新正向边的容量
            edge[i ^ 1].cap += new_flow;  // 更新反向边的容量
            if (used_flow == flow) break;  // 如果流量满了，停止搜索
        }
    }
    return used_flow;  // 返回本次增广的流量
}

// ZKW 费用流主函数，计算最小费用最大流
void zkw(int S, int T) {
    int total_flow = 0, total_cost = 0;
    
    while (SPFA(S, T)) {  // 不断使用 SPFA 分层
        flag = true;
        while (flag) {  // 当有增广路径时，不断进行 DFS 增广
            flag = false;
            dfs(S, T, INF, total_flow, total_cost);
        }
    }
    printf("Maximum Flow: %d\nMinimum Cost: %d\n", total_flow, total_cost);  // 输出最大流和最小费用
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(head, -1, sizeof(head));  // 初始化链式前向星的 head 数组为 -1
        tot = -1;  // 初始化边的总数
        
        for (int i = 1; i <= m; i++) {
            int u, v, cap, cost;
            scanf("%d%d%d%d", &u, &v, &cap, &cost);  // 输入每条边的起点、终点、容量和费用
            addEdge(u, v, cap, cost);  // 添加边
        }
        
        int S = 1, T = n;  // 源点和汇点
        zkw(S, T);  // 调用 ZKW 费用流主函数
    }
    return 0;
}

http://www.kler.cn/a/451844.html

相关文章：

  • 基于WEB的房屋出租管理系统设计
  • debug diagnostic tool 调试.net的错误
  • Java重要面试名词整理（四）：并发编程（下）
  • QT-基础-1-Qt 中的字符串处理与常见数据类型
  • go语言并发文件备份，自动比对自动重命名（逐行注释）
  • 谷歌浏览器的网络安全检测工具介绍
  • 【AIGC-ChatGPT副业提示词指令】炼金术士的元素启示：在神秘中寻找生命的答案【限时免费阅读，一天之后自动进入进阶课程】
  • Jenkins集成部署(图文教程、超级详细）
  • 【每日学点鸿蒙知识】蓝牙Key、页面元素层级工具、私仓搭建、锁屏显示横幅、app安装到真机
  • 基于Spring Boot的网络购物商城的设计与实现
  • 软件测试之测试用例
  • 突发！！！GitLab停止为中国大陆、港澳地区提供服务，60天内需迁移账号否则将被删除
  • 基于LR/GNB/SVM/KNN/DT算法的鸢尾花分类和K-Means算法的聚类分析
  • SpringBoot从入门到实战：动态解析MyBatis SQL字符串获取可执行的SQL
  • 深度学习的DataLoader是什么数据类型，为什么不可用来索引
  • python中bug修复案例-----图形界面程序中修复bug
  • Python数字图像处理课程平台的开发
  • WPS怎么都无法删除空白页_插入空白页一次插入两张?_插入横屏空白页_横屏摆放图片_这样解决_显示隐藏段落标记---WPS工作笔记001
  • 【多时段】含sop的配电网重构【含分布式电源】【已更新视频讲解】
  • “协同过滤技术实战”：网上书城系统的设计与实现
  • C# OpenCV机器视觉:颜色检测
  • vue前端项目中实现电子签名功能（附完整源码）
  • 物联网：全面概述、架构、应用、仿真工具、挑战和未来方向
  • 字符编码(四)
  • 谷歌开发者工具 -来源/源码篇
  • 【网络云计算】2024第51周-每日【2024/12/20】小测-理论-周测-解析