一、费用流板子SPFA DFS 当前弧优化时间复杂度与流量大小和费用范围有关一般能处理 n≤5000,m≤10e5 的规模。特点支持负费用边但不能有负环使用 SPFA 找最短路。最大流最小费用#include bits/stdc.h using namespace std; constexpr int N 5005; // 最大点数按实际需求调整 constexpr int M 200005; // 最大边数 × 2每条边要建反向边 constexpr int INF 0x3f3f3f3f; struct MCMF { int tot, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M]; int dis[N], fee; // fee 记录最小费用 bool vis[N]; void init(int n 0) { // 传 n 可不传这里只是重置 tot 1; memset(lnk, 0, sizeof(lnk)); } // 加边u-v容量 w单位费用 c void addedge(int u, int v, int w, int c) { ter[tot] v, nxt[tot] lnk[u], lnk[u] tot, cap[tot] w, cost[tot] c; ter[tot] u, nxt[tot] lnk[v], lnk[v] tot, cap[tot] 0, cost[tot] -c; } bool spfa(int s, int t) { memset(dis, 0x3f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); queueint q; q.push(s), dis[s] 0, vis[s] true; while (!q.empty()) { int u q.front(); q.pop(), vis[u] false; for (int i lnk[u]; i; i nxt[i]) { int v ter[i]; if (cap[i] dis[v] dis[u] cost[i]) { dis[v] dis[u] cost[i]; if (!vis[v]) q.push(v), vis[v] true; } } } return dis[t] ! INF; } int dfs(int u, int t, int flow) { if (u t) return flow; vis[u] true; int ans 0; for (int i cur[u]; i ans flow; i nxt[i]) { int v ter[i]; if (!vis[v] cap[i] dis[v] dis[u] cost[i]) { int x dfs(v, t, min(cap[i], flow - ans)); if (x) { fee x * cost[i]; cap[i] - x, cap[i ^ 1] x, ans x; } } } vis[u] false; return ans; } // 返回 {最大流, 最小费用} pairint, int solve(int s, int t) { int flow 0; fee 0; while (spfa(s, t)) { int x; while ((x dfs(s, t, INF))) flow x; } return {flow, fee}; } };二、基本用法1. 建图与求解MCMF g; int main() { int n, m, s, t; scanf(%d%d%d%d, n, m, s, t); g.init(); for (int i 0; i m; i) { int u, v, w, c; scanf(%d%d%d%d, u, v, w, c); g.addedge(u, v, w, c); // 加边容量 w单位费用 c } auto [maxflow, mincost] g.solve(s, t); printf(maxflow %d, mincost %d\n, maxflow, mincost); return 0; }2. 常见接口总结操作说明g.init()初始化多组数据时必调g.addedge(u, v, w, c)添加一条从u到v、容量为w、单位费用为c的有向边g.solve(s, t)从源点s到汇点t跑最小费用最大流返回{最大流, 最小费用}三、进阶用法限定流量求最小费用有时候你不需要跑满最大流而是希望流量恰好为K时费用最小// 在 solve 的基础上稍作修改 pairint, int solve_limit(int s, int t, int K) { int flow 0; fee 0; while (flow K spfa(s, t)) { int x; while (flow K (x dfs(s, t, K - flow))) flow x; } if (flow K) return {-1, -1}; // 流量达不到 K无解 return {flow, fee}; }最大费用最大流把费用取相反数建边跑完再把结果取反即可g.addedge(u, v, w, -c); // 费用取负 // 跑完后 mincost -maxcost四、注意事项节点编号板子本身不限制编号但通常从1开始与题目一致即可。边数要开够M至少要开到(题目最大边数 × 2)因为每条边要建一条反向边。多组测试数据一定要调用init()重置lnk和tot。溢出问题如果费用或流量很大记得把fee、cap、cost改成long long。负环SPFA 能处理负权边但图中不能存在从源点可达的负环否则会死循环。原理一、原理1. 核心目标在保证流量最大的前提下让总费用最小。打个比方你是一个物流公司老板要把尽可能多的货物从仓库源点 S运到客户汇点 T每条路有容量限制最多运多少车和过路费每车多少钱。你既想多赚钱流量大又想省钱费用低——这就是最小费用最大流。2. 贪心策略每次走最便宜的路算法流程本质上就是一个带费用的增广路算法while (在残量网络中还能找到一条 S→T 的费用最短路径) { 沿着这条最短路尽可能多地运货受限于路径上最小的剩余容量 更新剩余容量同时累加费用 }为什么这样做能保证最小费用因为每次选的都是当前单位费用总和最低的路径。数学上可以证明类似 Edmonds-Karp这样得到的费用序列是单调不减的最终停下来的时候就是全局最小费用。反向边为啥费用是-c这是最妙的设计。假设你之前从 A→B 运了一批货后来发现绕路更便宜你想反悔——把 A→B 的货运回来到别的路走。反向边 B→A 容量恢复、费用设为-c意味着退掉 1 单位流量 收回c块钱相当于撤销之前的操作账本自动对齐3. 板子每一步在干嘛函数干了啥spfa(s, t)在残量网络上找 S→T 的费用最短路用dis[]记录每个点到源的最小费用距离dfs(s, t, flow)沿着dis[v] dis[u] cost[i]的边也就是在最短路上的边进行多路增广一次 SPFA 可能增广多次cur[]当前弧避免重复走已经流满的边加速vis[]防止 DFS 在残量网络里绕圈死循环因为可能有零环/负环残留二、常见题型 → 网络流建图套路套路 1二分图最优匹配最经典场景N 个人做 N 项工作每个人做每项工作的收益/成本不同每人只能做一项每项只需一人求最大总收益或最小总成本。建图源点 S ──(容量1, 费用0)──→ 每个人 每个人 ──(容量1, 费用成本)──→ 每项工作 每项工作 ──(容量1, 费用0)──→ 汇点 T最大收益 → 费用取负跑最小费用最大流最后答案取反。如果人数和工作数不等就是一般的二分图带权匹配。例题洛谷 P4014 分配问题、P2053 [SCOI2007] 修车套路 2供需运输问题场景有若干个工厂供应量和商店需求量工厂到商店有单位运费求满足所有需求的最小运费。建图源点 S ──(容量供应量, 费用0)──→ 工厂 工厂 ──(容量∞, 费用单位运费)──→ 商店 商店 ──(容量需求量, 费用0)──→ 汇点 T例题洛谷 P4015 运输问题套路 3点/边有使用次数限制的最优化场景经过一个点最多 K 次或者选某些物品有依赖关系求最大收益。常用技巧拆点比如每个点最多经过一次把点 u 拆成 u_in 和 u_out S → u_in (容量1, 费用0) u_in → u_out (容量1, 费用点权/-点权) ← 在这里体现选这个点的代价/收益 u_out → 它能到达的点 (容量∞, 费用0)相当于uin uout之间加一个单边限制了最大u容量例题洛谷 P4011 孤岛营救不是这个、P1251 餐巾计划超级经典套路 4网格图取数黑白染色场景N×M 网格每个格子有数字选了某个格子就不能选相邻格子求选出数的最大和。建图黑白染色像国际象棋棋盘 黑色格子 ── 连源点 S (容量1, 费用0) 白色格子 ── 连汇点 T (容量1, 费用0) 黑色 → 相邻白色 (容量1, 费用-(格子值))跑最小费用最大流答案是-fee。本质是二分图最大权独立集 总权 - 最小割 跑费用流例题洛谷 P2774 方格取数问题套路 5最大费用最大流利润最大化场景和最小费用一样但你要求的是收入最大。做法所有费用c变成-c建边跑完 MCMF 后max_profit -mincost。注意SPFA 找的是最短路所以取负之后最大收入路就变成了最短路完美适配。套路 6流量限制不是跑满最大流场景不一定非要运最多的货而是刚好运 K 个单位时费用最小。做法在solve里加个流量上限判断我之前给你的solve_limit函数或者更简单——在源点 S 连一个超级源 SS边容量为 K这样整个网络最多就只能流 K 了。SS ──(容量K, 费用0)──→ S套路 7线性规划 / 差分约束进阶有些形如满足若干不等式求目标函数最值的问题可以写成费用流。比如经典题志愿者招募P3980每天有最少人数需求志愿者按连续天数签约每人有费用求满足需求的最小花费建图核心思想把天与天之间连边表示前一天剩下的人招募志愿者就是走一条跨越几天的边。三、快速识别费用流看到题目里有这些关键词立刻往费用流上靠信号说明最多选 K 个 求最大/最小价值流量限制 费用流一一对应/每人分配一个任务二分图匹配 → 费用流经过每个点最多一次 有权值拆点 费用流连续几天/区间覆盖 最小花费志愿者招募类链式建图不能同时选相邻的 网格黑白染色 最小割/费用流答案要求最大收益或最小成本费用流取负或直接跑
一、费用流板子SPFA DFS 当前弧优化时间复杂度与流量大小和费用范围有关一般能处理 n≤5000,m≤10e5 的规模。特点支持负费用边但不能有负环使用 SPFA 找最短路。最大流最小费用#include bits/stdc.h using namespace std; constexpr int N 5005; // 最大点数按实际需求调整 constexpr int M 200005; // 最大边数 × 2每条边要建反向边 constexpr int INF 0x3f3f3f3f; struct MCMF { int tot, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M]; int dis[N], fee; // fee 记录最小费用 bool vis[N]; void init(int n 0) { // 传 n 可不传这里只是重置 tot 1; memset(lnk, 0, sizeof(lnk)); } // 加边u-v容量 w单位费用 c void addedge(int u, int v, int w, int c) { ter[tot] v, nxt[tot] lnk[u], lnk[u] tot, cap[tot] w, cost[tot] c; ter[tot] u, nxt[tot] lnk[v], lnk[v] tot, cap[tot] 0, cost[tot] -c; } bool spfa(int s, int t) { memset(dis, 0x3f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); queueint q; q.push(s), dis[s] 0, vis[s] true; while (!q.empty()) { int u q.front(); q.pop(), vis[u] false; for (int i lnk[u]; i; i nxt[i]) { int v ter[i]; if (cap[i] dis[v] dis[u] cost[i]) { dis[v] dis[u] cost[i]; if (!vis[v]) q.push(v), vis[v] true; } } } return dis[t] ! INF; } int dfs(int u, int t, int flow) { if (u t) return flow; vis[u] true; int ans 0; for (int i cur[u]; i ans flow; i nxt[i]) { int v ter[i]; if (!vis[v] cap[i] dis[v] dis[u] cost[i]) { int x dfs(v, t, min(cap[i], flow - ans)); if (x) { fee x * cost[i]; cap[i] - x, cap[i ^ 1] x, ans x; } } } vis[u] false; return ans; } // 返回 {最大流, 最小费用} pairint, int solve(int s, int t) { int flow 0; fee 0; while (spfa(s, t)) { int x; while ((x dfs(s, t, INF))) flow x; } return {flow, fee}; } };二、基本用法1. 建图与求解MCMF g; int main() { int n, m, s, t; scanf(%d%d%d%d, n, m, s, t); g.init(); for (int i 0; i m; i) { int u, v, w, c; scanf(%d%d%d%d, u, v, w, c); g.addedge(u, v, w, c); // 加边容量 w单位费用 c } auto [maxflow, mincost] g.solve(s, t); printf(maxflow %d, mincost %d\n, maxflow, mincost); return 0; }2. 常见接口总结操作说明g.init()初始化多组数据时必调g.addedge(u, v, w, c)添加一条从u到v、容量为w、单位费用为c的有向边g.solve(s, t)从源点s到汇点t跑最小费用最大流返回{最大流, 最小费用}三、进阶用法限定流量求最小费用有时候你不需要跑满最大流而是希望流量恰好为K时费用最小// 在 solve 的基础上稍作修改 pairint, int solve_limit(int s, int t, int K) { int flow 0; fee 0; while (flow K spfa(s, t)) { int x; while (flow K (x dfs(s, t, K - flow))) flow x; } if (flow K) return {-1, -1}; // 流量达不到 K无解 return {flow, fee}; }最大费用最大流把费用取相反数建边跑完再把结果取反即可g.addedge(u, v, w, -c); // 费用取负 // 跑完后 mincost -maxcost四、注意事项节点编号板子本身不限制编号但通常从1开始与题目一致即可。边数要开够M至少要开到(题目最大边数 × 2)因为每条边要建一条反向边。多组测试数据一定要调用init()重置lnk和tot。溢出问题如果费用或流量很大记得把fee、cap、cost改成long long。负环SPFA 能处理负权边但图中不能存在从源点可达的负环否则会死循环。原理一、原理1. 核心目标在保证流量最大的前提下让总费用最小。打个比方你是一个物流公司老板要把尽可能多的货物从仓库源点 S运到客户汇点 T每条路有容量限制最多运多少车和过路费每车多少钱。你既想多赚钱流量大又想省钱费用低——这就是最小费用最大流。2. 贪心策略每次走最便宜的路算法流程本质上就是一个带费用的增广路算法while (在残量网络中还能找到一条 S→T 的费用最短路径) { 沿着这条最短路尽可能多地运货受限于路径上最小的剩余容量 更新剩余容量同时累加费用 }为什么这样做能保证最小费用因为每次选的都是当前单位费用总和最低的路径。数学上可以证明类似 Edmonds-Karp这样得到的费用序列是单调不减的最终停下来的时候就是全局最小费用。反向边为啥费用是-c这是最妙的设计。假设你之前从 A→B 运了一批货后来发现绕路更便宜你想反悔——把 A→B 的货运回来到别的路走。反向边 B→A 容量恢复、费用设为-c意味着退掉 1 单位流量 收回c块钱相当于撤销之前的操作账本自动对齐3. 板子每一步在干嘛函数干了啥spfa(s, t)在残量网络上找 S→T 的费用最短路用dis[]记录每个点到源的最小费用距离dfs(s, t, flow)沿着dis[v] dis[u] cost[i]的边也就是在最短路上的边进行多路增广一次 SPFA 可能增广多次cur[]当前弧避免重复走已经流满的边加速vis[]防止 DFS 在残量网络里绕圈死循环因为可能有零环/负环残留二、常见题型 → 网络流建图套路套路 1二分图最优匹配最经典场景N 个人做 N 项工作每个人做每项工作的收益/成本不同每人只能做一项每项只需一人求最大总收益或最小总成本。建图源点 S ──(容量1, 费用0)──→ 每个人 每个人 ──(容量1, 费用成本)──→ 每项工作 每项工作 ──(容量1, 费用0)──→ 汇点 T最大收益 → 费用取负跑最小费用最大流最后答案取反。如果人数和工作数不等就是一般的二分图带权匹配。例题洛谷 P4014 分配问题、P2053 [SCOI2007] 修车套路 2供需运输问题场景有若干个工厂供应量和商店需求量工厂到商店有单位运费求满足所有需求的最小运费。建图源点 S ──(容量供应量, 费用0)──→ 工厂 工厂 ──(容量∞, 费用单位运费)──→ 商店 商店 ──(容量需求量, 费用0)──→ 汇点 T例题洛谷 P4015 运输问题套路 3点/边有使用次数限制的最优化场景经过一个点最多 K 次或者选某些物品有依赖关系求最大收益。常用技巧拆点比如每个点最多经过一次把点 u 拆成 u_in 和 u_out S → u_in (容量1, 费用0) u_in → u_out (容量1, 费用点权/-点权) ← 在这里体现选这个点的代价/收益 u_out → 它能到达的点 (容量∞, 费用0)相当于uin uout之间加一个单边限制了最大u容量例题洛谷 P4011 孤岛营救不是这个、P1251 餐巾计划超级经典套路 4网格图取数黑白染色场景N×M 网格每个格子有数字选了某个格子就不能选相邻格子求选出数的最大和。建图黑白染色像国际象棋棋盘 黑色格子 ── 连源点 S (容量1, 费用0) 白色格子 ── 连汇点 T (容量1, 费用0) 黑色 → 相邻白色 (容量1, 费用-(格子值))跑最小费用最大流答案是-fee。本质是二分图最大权独立集 总权 - 最小割 跑费用流例题洛谷 P2774 方格取数问题套路 5最大费用最大流利润最大化场景和最小费用一样但你要求的是收入最大。做法所有费用c变成-c建边跑完 MCMF 后max_profit -mincost。注意SPFA 找的是最短路所以取负之后最大收入路就变成了最短路完美适配。套路 6流量限制不是跑满最大流场景不一定非要运最多的货而是刚好运 K 个单位时费用最小。做法在solve里加个流量上限判断我之前给你的solve_limit函数或者更简单——在源点 S 连一个超级源 SS边容量为 K这样整个网络最多就只能流 K 了。SS ──(容量K, 费用0)──→ S套路 7线性规划 / 差分约束进阶有些形如满足若干不等式求目标函数最值的问题可以写成费用流。比如经典题志愿者招募P3980每天有最少人数需求志愿者按连续天数签约每人有费用求满足需求的最小花费建图核心思想把天与天之间连边表示前一天剩下的人招募志愿者就是走一条跨越几天的边。三、快速识别费用流看到题目里有这些关键词立刻往费用流上靠信号说明最多选 K 个 求最大/最小价值流量限制 费用流一一对应/每人分配一个任务二分图匹配 → 费用流经过每个点最多一次 有权值拆点 费用流连续几天/区间覆盖 最小花费志愿者招募类链式建图不能同时选相邻的 网格黑白染色 最小割/费用流答案要求最大收益或最小成本费用流取负或直接跑
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
