C++怎么使用Dinic算法快速求最大网络流-C++-PHP中文网

Dinic比Edmonds-Karp快因其分层图+BFS预处理+多路增广，复杂度O(V²E)优于O(VE²)；需邻接表存边、正反向边成对存储（下标异或1）、当前弧优化防重复扫描。

c++怎么使用dinic算法快速求最大网络流

为什么Dinic比DFS增广路（如Edmonds-Karp）快？

Dinic的核心加速在于「分层图 + 多路增广」：它先用BFS构建以源点为起点的最短路径层次图（level[]数组），再在该图上用DFS一次性找多条阻塞流，避免反复进入死胡同。对稀疏图或单位容量图，复杂度可压到 O(V²E)；实践中常远优于Edmonds-Karp的 O(VE²)，尤其在存在大量短增广路时。

关键结构体怎么写才不爆内存又支持重边？

必须用邻接表存边，且正向边与反向边成对存储（下标异或1），方便快速访问反向边。不要用map或vector>动态扩容——每加一条原图边，就往edges里push两次（正向+初始容量为0的反向边）。

struct Edge {
    int to, cap, rev; // rev是反向边在edges中的下标
};
vector<edge> edges;
vector<vector>> graph; // graph[u]存从u出发的所有边在edges中的索引</vector></edge>

常见错误：
• 忘记初始化rev字段，导致反向边更新错位
• 把graph做成vector<vector>></vector>，导致BFS/DFS中无法O(1)拿到边索引
• 边数组开太小（比如只开m，实际要开2*m）

`BFS`建分层图时要注意哪些边界？

BFS只走残量 > 0 的边，且只给未访问节点赋level。关键判断是：if (e.cap > 0 && level[e.to] == -1)。漏掉cap > 0会把已满边也纳入层次图；漏掉== -1会导致重复入队甚至死循环。

实用建议：
• 初始化level全为-1，源点level[s] = 0
• BFS结束后若level[t] == -1，说明已无增广路，直接退出主循环
• 不要用queue>存（节点, 当前流量），BFS阶段只关心可达性

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

`DFS`找阻塞流为什么必须用当前弧优化？

没优化的DFS会在同一层反复扫描已饱和的边，退化成指数级。当前弧优化（iter[u]）记录每个节点上次成功扩展的边索引，下次从那里继续——本质是“每个点只试一遍所有出边”。

代码片段示意：

int dfs(int u, int t, int f) {
    if (u == t) return f;
    for (int& i = iter[u]; i  0 && level[u] + 1 == level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                edges[e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

注意：
• iter[u]必须是引用（int&），否则循环内修改不生效
• 每次进入新BFS轮次前，要重置iter数组为0
• 返回0不代表失败，只是当前路径不通，需继续试下一条边（所以不能break）

真正卡住性能的往往不是算法本身，而是建图时边序号混乱、BFS后忘了检查level[t]是否可达、或者DFS里没用引用导致当前弧失效——这几个点调通，Dinic就能稳定跑赢SPFA-based的其他流算法。