发现竟然有这么有趣的东西，来补一发题解。
无源汇上下界可行流
我们先从它开始，现在有这样一个问题：给定一个无源汇的网络流，每个点都需要满足 流量平衡 ，也就是流出的流量必须等于流入的流量。每一条边都有一个限制 ([l_i,r_i]) ，要求这条边的流量在这个范围内，求一个可行流。
首先有一个骚操作，由于网络流只能处理诸如 ([0,x]) 的限制，所以我们把每条边的限制变成 ([0,r_i-l_i]) 然后套普通的网络流即可，也就是我们先默认了 (l_i) 的流量，再让他去选择在此基础上多多少流量 。
但是显然会有问题，因为单纯这样做的话并没有考虑原有的 (l_i) 的流量，由于这些流量没有考虑我们使用 补流 的思想，尝试把原来的流量补到这个图中。可以兴建源点和汇点，设 (in[i]) 为流入 (i) 边的 (l) 之和，(out[i]) 为流出 (i) 边的 (l) 之和。如果 (in[i]>out[i]) ，说明基础流量中 总体上 是流入了 (in[i]-out[i]) 的流量，让他连接源点；否则说明总体上是流出了 (out[i]-in[i]) 的流量，让他连接汇点。
然后对建出来的图跑最大流，需要验证这个图有没有满流，也就是源点连出去的边有没有满流，如果满足这个条件那么汇点连的边也是满流的（流量平衡），这样的话基础流量就可以保证，然后剩下的边就可以随心所欲了。
有源汇上下界最大流
首先你要知道 有源汇上下界可行流 怎么做。
有一个小 ( t trick) ，因为源汇点我们要兴建，所以原来的源汇点是不可以有的。关键的问题在于流量平衡，为了让原来的源汇点流量平衡，我们连一条 ((t,s,inf)) 的边表示 (s->t) 的流量全部返还回来，就变成了无源汇的问题。
然后现在要最大流又怎么办呢？先求出一个可行流，然后我们要对那些原来随心所欲的边搞点事情。我们去掉新加的边 ((t,s,inf)) ，然后再对 (s->t) 跑一遍最大流，因为还可以榨干这些随心所欲的边，答案是第一次最大流新加边的流量（原来的最大流又返还回去了） (+) 第二次的最大流。
为什么可以直接加上第二次的最大流呢？因为我们去掉了 (t->s) 这条返还流量的边，如果我们增加 (s->t) 的流量，那么在我们新建的图中是可以返还回去的，也就是用那条边来使得流量环流。
给出一道例题：[模板]有源汇上下界最大流
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int M = 2005;
const int inf = 0x3f3f3f3f;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,tot,f[M],s1,t1,s,t,ans,sum,in[M],out[M],dis[M],cur[M];
struct edge
{
int v,c,next;
}e[M*M];
void add(int u,int v,int c)
{
e[++tot]=edge{v,c,f[u]},f[u]=tot;
e[++tot]=edge{u,0,f[v]},f[v]=tot;
}
int bfs()
{
queue<int> q;
memset(dis,0,sizeof dis);
q.push(s);dis[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
if(u==t) return 1;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(!dis[v] && e[i].c>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int ept)
{
if(u==t) return ept;
int flow=0;
for(int &i=cur[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+1 && e[i].c>0)
{
int tmp=dfs(v,min(e[i].c,ept));
if(!tmp) continue;
ept-=tmp;
e[i].c-=tmp;
e[i^1].c+=tmp;
flow+=tmp;
if(!ept) break;
}
}
return flow;
}
int dinic()
{
int res=0;
while(bfs())
{
for(int i=1;i<=t;i++) cur[i]=f[i];
res+=dfs(s,inf);
}
return res;
}
signed main()
{
while(~scanf("%d %d",&n,&m))
{
tot=1;ans=sum=0;
s1=n+m+1;t1=n+m+2;s=n+m+3;t=n+m+4;
for(int i=1;i<=t;i++)
in[i]=out[i]=f[i]=0;
for(int i=1;i<=m;i++)
{
int x=read();
out[i+n]+=x;in[t1]+=x;
add(i+n,t1,inf-x);
}
for(int i=1;i<=n;i++)
{
int c=read(),d=read();
add(s1,i,d);
while(c--)
{
int t=read()+1,l=read(),r=read();
out[i]+=l;in[t+n]+=l;
add(i,t+n,r-l);
}
}
for(int i=1;i<=t1;i++)
{
if(in[i]>out[i]) add(s,i,in[i]-out[i]),sum+=in[i]-out[i];
else add(i,t,out[i]-in[i]);
}
add(t1,s1,inf);
if(dinic()<sum)
{
puts("-1
");
continue;
}
ans=e[tot].c;//也就是返回流量的边流了多少
e[tot].c=e[tot^1].c=0;//删去流量平衡边
s=s1;t=t1;//更改源汇点
ans+=dinic();
printf("%d
",ans);
}
}
//注意清空
有源汇上下界最小流
更有源汇上下界最大流很像啊，我们先求出有源汇上下界可行流。
类似地，我们跑 (t->s) 的最大流，然后减掉他就是答案，还是对环流的一个操作。
给出一道例题：清理雪道 ，要清理 ((x,y)) 就建一条 (x->y) 的边流量下界为 (1) 就行了。
最小费用可行流
我准备结合这一道例题来讲：Incorrect Flow
首先原图的边可以看成 ((u,v)) ，容量上界和下界都是 (c) ，当然这样不一定是合法的，为了不爆容量和流量平衡，我们还可以用增减 (c,f) 的操作，体现在图上可以这样建边（需要讨论 (f,c) 的关系）：
对于 (fleq c) 的情况：
- 如果减少 (f) ，连 ((v,u)) ，容量为 (f) ，费用为 (1)
- 如果增大 (f) ，连 ((u,v)) ，容量为 (c-f) ，费用为 (1)
- 再增大 (f) 的话就要改 (c) 了，连 ((u,v)) ，容量为 (inf) ，费用为 (2)
对于 (f>c) 的情况，先让他满足不爆容量，所以花 (f-c) 改一下 (c)：
- 如果减小 (f) ，连 ((v,u)) ，那么 (c) 没有必要增加那么大了，容量为 (f-c) ，费用为 (0)
- 再减小 (f) 的话 (c) 就相当于不改了，连 ((v,u)) ，容量为 (inf) ，费用为 (1)
- 如果增大 (f) ，那么 (f,c) 都要再增大，连 ((u,v)) ，容量为 (inf) ，费用为 (2)
最后连 (t->s) 的一条容量为 (inf) 的边来返还流量，这样就变成了一道最小费用可行流的问题了。
新建超级源点和超级汇点，考虑那些原来确定了流量的边，如果流入比流出多，那么 (S->u) ，容量为流入流出的差值，费用为 (0) 。如果流出比流入多，那么 (u->T) ，容量为流出流入的差值，费用为 (0) ，然后跑最小费用最大流。
其他例题
可以考虑二分答案 (mid) ，那么对于每一行都有这样的限制：(sum_{j=1}^ma_{i,j}-midleq sum_{j=1}^m b_{i,j}leq sum_{j=1}^ma_{i,j}+mid) ，对于列也有类似的柿子，我们把源点向每一行连边，容量就是上述的范围，汇点向每一列连边。
行和列之间两两连边，容量范围是 ([L,R]) ，每一条边都表示一个位置数的选择，然后跑有源汇上下界可行流即可。
挺简单的，有源汇上下界网络流，推一下我的洛谷博客