写这个博客主要是为了自己复习用。这个东西看起来虽然不好理解，但实际上有着非常美妙的性质。（所以比较容易忘QAQ）所以我就打算把它稍微做一点个人笔记啦~
如果对你有帮助的话，记得点个赞哦~
\(Part\) \(1\) ：无源汇上下界可行流
概念理解：
没有\(S\)和\(T\)节点来统一发出和回收流量。
如果我们把网络流类比成蹄形磁铁的磁感线的话，无源汇上下界可行流就相当于考虑磁铁内部从\(S\)极到\(N\)极磁感线时的情况。
如果不太好理解，您还可以理解为一个循环的管道里面流淌着奇怪的液体（比如液态钾钠合金），然后一直流啊流啊流啊流着在里面循环。
依然要保持流量出入平衡。（每个点进多少出多少）
而且。。。你要保证他的流量在一个\([l, r]\)的范围内
这咋整啊？
我们先啥都不管，对每条边先把下界塞上再讲。这个时候，流量出入显然不平衡，但已经满足了基本的下界要求。填完下界，剩下的容量就可以为所欲为啦。接下来只要在这个基础上，再填上一些必要的流量保持平衡就可以了。
add_edge (u, v, upp[i] - low[i]); // u -> v, flow = upp[i] - low[i]
因为\(low[i]\)被我们事先用完了，所以我们的容量就统一减少了\(low[i]\)这一块。
前面我们已经不计后果地把下界堵着了。自己欠下的锅迟早要背的，这里我们就需要一个补偿流来维护流量的出入平衡。对于每一个点，我们计算它的所有流入流量减去流出流量，得到一个\(flow[i]\)。
flow[u] -= low[i];
flow[v] += low[i];
\(flow[i]>0\)说明流进来的比较多，需要一个流出的补偿流。
\(flow[i] < 0\)说明流出去的比较多，需要一个流入的补偿流。
仔细一想，搞补偿流还不简单？直接在前后的边上加流量就好啦。但是事情并没有那么简单——首先这么操作很麻烦，其次\(dinic\)算法是针对有源网络流进行的，循环流它是无能为力的。
然后就有了一个非常伟大的想法——里应不行，我外合不久是了？
所以我们新建一个\(S\)点和一个\(T\)点，接下来的操作就变成了这样：
\(flow[i]>0\)说明流进来的比较多，需要一个流出的补偿流。为了引出这个流出的补偿流，我们添加一个流量为\(+flow[i]\)的，由当前点流出到终点的流。
\(flow[i] < 0\)说明流出去的比较多，需要一个流入的补偿流。为了引出这个流入的补偿流，我们添加一个流量为\(-flow[i]\)的，由源点流入到当前点的流。
int s = 0, t = n + 1;
for (int i = 1; i <= n; ++i) {
if (flow[i] < 0) {
//流出多 -> 需要流入的补偿流 -> 通过增加外源流出来引出
add_edge (i, t, -flow[i]);
add_edge (t, i, 0);
} else if (flow[i] > 0){
//流入多 -> 需要流出的补偿流 -> 通过增加外源流入来引出
max_flow += flow[i];
add_edge (s, i, +flow[i]);
add_edge (i, s, 0);
}
}
通过添加相反方向的边，对之前的不平衡作出抵消，我们就实现了出入平衡啦~（也可以像上面那样理解，同样很清楚。）
这样把边一连，套上\(dinic\)，我们就跑出来了一个可行流（是当前图的最大流，但不一定真的是所有可以造出来的流中的最大！）根据出入平衡，这里一定有\(∑flow[i] (flow[i] > 0) = max\_flow\) 。通过这个等式，我们就可以检验可行流的存在性啦~
if (max_flow != can_flow) {
puts ("please go home to sleep");
return 0;
}
好啦，睡前的最后一个问题：既然我们把本来应该在里面穿插着的补偿流引到了外面，我们又怎么求出所有边使用的可行流大小呢？
像前面所说的：我们添加引向\(S\)和\(T\)的边，是为了引出补偿流。所以说，虽然补偿流来的时候不好算，但是走的时候是会留下痕迹哒。（想一下反向边！）所以我们只需要在当前边流量下界的基础上，添加一个当前边的反向边流量（就是之前溜走的补偿流流量啦~），就得到最终的可行流啦~
for (int i = 1; i <= m; ++i) {
printf ("%d\n", e[((i - 1) * 2) ^ 1].f + low[i]);
}
剩下还有三个延伸拓展的先咕着，回头再说啦\(QwQ\)
上下界网络流——概念解析与快速入门
原文：https://www.cnblogs.com/maomao9173/p/10336427.html
