最小割

OI&ACM, 网络流
算法合集之《最小割模型在信息学竞赛中的应用》 1 【bzoj 1412】[ZJOI2009]狼和羊的故事 Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。Orez想要添加篱笆的尽可能的短。当然这个 ...
Read More

上下界网络流

OI&ACM, 网络流
上下界网络流就是边的流量有上下界限制的网络流 平常的网络流可以当做下界为0的特殊情况 无源汇 可行流 可以想到为了满足流量的下限 \(low\)，将边的流量设为 \(high-low\)。 但是求出这个图的最大流之后，加上 \(low\)，会使得某些点不满足流量平衡。 所以可以建 ...
Read More
网络流 上下界网络流