最小割

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

上下界网络流

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

网络流

Dinic 详解 #include<cstdio>#include<queue>using namespace std;const int N=5005;const int M=10005;int n,m,S,T,ans,tot=1,ds[N],st[N],to[ ...