上下界网络流

"上下界网络流" 上下界网络流是一种特殊的网络流，边的流量有限制，必须在[down, up]的范围内。普通的网络流也是一种特殊的上下界网络流，只是每条边的流量限制为[0, cap]。上下界网络流可以分为两种：有源汇和无源汇。 无源汇的上下界网络流： 在无源汇的上下界网络流中，除了源点和汇点外，所有点都要求满足流量平衡。可以通过添加三条边来解决问题：u->v cap=up-down, S->v cap=down, u->T cap=down。然后，求出这个图的最大流，如果最大流等于∑downi，那么就是可行流，否则没有可行流。 有源汇的上下界网络流： 在有源汇的上下界网络流中，可以通过添加一条 t->s 的边，流量限制为[0, inf]，将其转换为无源汇问题。然后，使用相同的方法来解决问题。 最小流： 最小流是指在网络流中，找到一个最小的流量，使得网络流中的所有边的流量都在其限制范围内。可以使用二分法来解决问题。不连接 t->s 的边，求出最大流，然后连接 t->s 的边，在残量网络上求最大流。比较两次求出的最大流的值，如果相等，那么就是最小流，否则没有可行流。 例题： * SGU 194：无源汇的上下界网络流 * POJ 2396：最小流 * SGU 176：最小流 * BZOJ 1458：最小流 * 例题：有一个管子要运输液体物质，物体的流速不能超过管子的容量，且物质不能再节点有积累，即每个节点的流入量等于流出量，在第一个节点生产的物质的流速与第 n 个节点的流速一样，求第一个节点的生产速度最小是多少，要是没有满足的情况输出：Impossible。 解决方法： 1. 增加超级源点 st 和超级汇点 sd，对于有上下界的边（i, j）流量（L, R）变为 R-L，然后 i 与 sd 连接容量是 L，st 与 j 连接容量是 L。 2. 做一次最大流 Dinic。 3. 在汇点 sd 到 st 连一条容量是 inf 的边。 4. 在做一次最大流 Dinic。 5. 当且仅当附加弧都满流时是有可行流，最后的最小流是 flow[sd->st]^1], st 到 sd 的最大流就是 sd 到 st 的最小流。