上下界网络流

概念

每条边有个流量限制 \([l,r]\)，要求该边流量 \(f\) 满足 \(l\le r\le r\)

无源汇上下界可行流

可以强行每条边先流 \(l_i\) ，再将将边设为 \(r_i-l_i\) ，但是我们发现每个点的流量不平衡，于是设 \(w\) 为入流流量-出流流量

• \(w>0\) 时，让 \(s'\) 向 \(i\) 连流量为 \(w\) 的边
• \(w<0\) 时，让 \(i\) 向 \(t'\) 连流量为 \(-w\) 的边

然后跑最大流，若满足新加的边的流量都流满，则有可行流

有源汇上下界可行流

将 \(t\) 向 \(s\) 连一条 \([0,+\infty]\) 的边，跑 无源汇上下界可行流

有源汇上下界最大流

先跑 有源汇上下界可行流，再在残量网络上跑最大流（注意用原来的原汇点）

答案就是 可行流+最大流

有源汇上下界最小流

先跑 有源汇上下界可行流，考虑退流的过程

把附加边删去，在残量网络上跑最大流，答案为 可行流-最大流

有源汇上下界最小费用可行流

和 有源汇上下界可行流 一样，不过在跑可行流时用费用流跑

最小费用为，预流的边的费用+费用流费用

例题

GMOJ3364 Snake

题目大意

有一个障碍的网格图，有两种蛇

1. 两个端点所在的格子在网格的边界。这样的蛇至少长度为 2。
2. 蛇构成一个环，即两个端点相邻 (垂直或水平)。注意这个条件意味着一条构成环的蛇至少需要占据 4 个格子。

要求用上面两种蛇覆盖网格图上非障碍的点，

solution

由源向所有白点连一条边，上界为2，假如是边界点，那么下界为1，否则为2。假如某个白点和某个黑点相邻，中间连一条上界为1，下界为0的边。对于黑点也用同样的方式和汇连边。做最大流，假如没有可行流那么无解，否则答案就是没有满流的与源或汇相连的边的数目除2

P4043 [AHOI2014/JSOI2014] 支线剧情

题目大意

有一个DAG图（只有1的入度为0），每条边有一个边权，每次操作可以选择一条从1开始的链，代价为链上的边权，问最后把每条边都选中最少一次的最小代价和

solution

DAG上的边连流量 \([1,+\infty]\) 费用为边权的边，每个点向汇点连流量为 \([0,+\infty]\) 费用为0的边，跑有源汇上下界最小费用可行流