OI Wiki 上下界网络流如何求满足流量下界的可行流【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki给定一张有向图每条边带有流量下界 $b(u,v)$ 与流量上界 $c(u,v)$你的任务是判断能否给每条边标出一个流量使得每条边满足 $b(u,v) \leq f(u,v) \leq c(u,v)$、除源点汇点外每个点流入等于流出并在有解时给出每条边的具体流量。OI Wiki 的 docs/graph/flow/bound.md 给出了完整解法把带下界的流网络转化为一个标准最大流问题用一次最大流的结果判断可行性再从残量网络中读出每条边的流量。下面按文档顺序还原这条操作路径。按文档要求开始前需要已熟练掌握最大流算法残量网络、增广路等概念可先复习 docs/graph/flow/max-flow.md。“可行流”到底要求什么对无源汇网络一个可行流必须同时满足两条每条边流量在上下界之间$b(u,v) \leq f(u,v) \leq c(u,v)$每个点流量平衡初始流入减初始流出为 0有源汇时源点和汇点除外。标准最大流算法只能处理下界为 0 的情况直接套用会破坏下界约束或流量平衡。文档的处理方式是先假设每条边已经流了等于下界的“初始流”再把每条边还能多流的余量放进新图把问题变成“这个不平衡能否在新图上被补足”。转化步骤把无源汇上下界可行流变成一次最大流按以下顺序建图铺初始流。假设每条边已流过下界 $b(u,v)$在新图中加入 $u \to v$、容量为 $c(u,v) - b(u,v)$ 的边表示该边在下界之上还能再走的流量。算每个点的不平衡量。设某点初始流入减初始流出为 $M$$M 0$该点已平衡不加附加边$M 0$流入过大新建附加源点 $S$由 $S$ 向该点连容量为 $M$ 的附加边$M 0$流出过大新建附加汇点 $T$由该点向 $T$ 连容量为 $-M$ 的附加边。跑最大流。在新图上求 $S$ 到 $T$ 的最大流。判定条件若 $S$ 连出去的边全部满流则存在可行流否则不存在。文档的解释是只有加上这份附加流之后原图才满足流量平衡某个点的附加边不满流就意味着该点的平衡无法成立。参考实现可直接编译运行的完整程序Wiki 在 docs/graph/code/flow/bound/bound_1.cpp 给出了无源汇情形的完整实现。输入第一行是点数 $n$ 和边数 $m$随后 $m$ 行每行 $u\ v\ l\ r$下界 $l$、上界 $r$有解时输出Yes并按输入顺序每行输出一条边的流量无解时输出No。程序与上面建图步骤的对应关系d[v] l[i]、d[u] - l[i]记录每个点“初始流入减初始流出”即上文说的 $M$add_edge(u, v, r - l[i])与add_edge(v, u, 0)新图中该边的正向边及其反向边。两次调用连续执行边编号差 1互为反向边代码用i ^ 1访问反向边d[i] 0的点从附加源s 0连容量 $d[i]$ 的边d[i] 0的点向附加汇t n 1连容量 $-d[i]$ 的边变量sum累计 $S$ 出发所有附加边的容量总和id[i]记录的是第 $i$ 条原边反向边的边号。最大流结束后反向边剩余容量e[id[i]].w就等于这条边在下界之上实际多走的流量所以e[id[i]].w l[i]就是该边在可行流中的最终流量判定ans是 $S \to T$ 的最大流值ans sum说明 $S$ 出发的边不可能全部满流输出No。完整程序如下与 Wiki 参考代码一致可直接编译运行从标准输入读入数据#include iostream #include queue using namespace std; constexpr int MAXN 3e4 10; constexpr int INF 1e9 10; int n, m, s 0, t; int ecnt 1, head[MAXN], dep[MAXN], now[MAXN], l[MAXN], d[MAXN], id[MAXN]; struct edge { int to, nxt, w; } e[MAXN]; void add_edge(int u, int v, int w) { e[ecnt] {v, head[u], w}; head[u] ecnt; } void init() { for (int i 0; i n 1; i) dep[i] 0; for (int i 0; i n 1; i) now[i] head[i]; } int bfs() { init(); queueint q; q.push(s); dep[s] 1; while (!q.empty()) { int x q.front(); q.pop(); for (int i head[x]; i; i e[i].nxt) { int v e[i].to; if (dep[v] || !e[i].w) continue; dep[v] dep[x] 1; q.push(v); } } return dep[t]; } int dfs(int x, int flow) { if (x t) return flow; int ret 0; for (int i now[x]; i; i e[i].nxt) { now[x] i; int v e[i].to; if (dep[v] ! dep[x] 1 || !e[i].w) continue; int w dfs(v, min(flow - ret, e[i].w)); e[i].w - w; e[i ^ 1].w w; ret w; if (ret flow) return ret; } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; s 0, t n 1; for (int i 1; i m; i) { int u, v, r; cin u v l[i] r; add_edge(u, v, r - l[i]); add_edge(v, u, 0); id[i] ecnt; d[v] l[i]; d[u] - l[i]; } long long sum 0; for (int i 1; i n; i) { if (d[i] 0) { add_edge(s, i, d[i]); add_edge(i, s, 0); sum d[i]; } else if (d[i] 0) { add_edge(i, t, -d[i]); add_edge(t, i, 0); } } long long ans 0; while (bfs()) ans dfs(s, INF); if (ans sum) { cout No\n; return 0; } cout Yes\n; for (int i 1; i m; i) cout e[id[i]].w l[i] \n; return 0; }使用前注意代码的规模常量MAXN 3e4 10同时约束点数与边数INF 1e9 10流量相关数组均为int类型题目的数据范围需要落在此限内否则要自行调整常量与类型。文档给出的配套例题是 Luogu P14578【模板】无源汇上下界可行流给定 $n$ 个点 $m$ 条有向边、每条边的下界 $l_i$ 与上界 $r_i$构造满足 $l_i \leq w_i \leq r_i$ 且每点流量平衡的方案或报告无解——正是上面程序的输入输出形式。有源汇网络先转成无源汇问题若题目已给定源点 $S$ 与汇点 $T$文档给出的转化只有一条加入一条 $T \to S$、上界 $\infty$、下界 $0$ 的边问题即转化为无源汇上下界可行流随后完全按上面的建图与判定流程处理。若有解$S$ 到 $T$ 的可行流流量等于这条 $T \to S$ 附加边的流量。结果判定与下一步可观测的结果就是程序的输出ans sum时打印No表示不存在可行流否则打印Yes随后 $m$ 行按输入顺序给出每条边的流量。这个输出方案由构造保证每条边流量 下界 该边在新图中的实际流量必然不超上界且各点因附加边满流而恢复流量平衡。如果任务不止“判存在”还要在可行流里问最大或最小流量docs/graph/flow/bound.md 给出了两个扩展操作两者都要求先拿到一个可行流求最大流时在删去所有附加边后的残量网络上再从 $S$ 跑一次到 $T$ 的最大流把两份流量相加求最小流时改从 $T$ 跑到 $S$把两份流量相减。文档特别警告第二次最大流必须在跑完上下界可行流之后的残量网络上跑不能在原来的流量网络上跑。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考