上下界网络流

上下界网络流就是边的流量有上下界限制的网络流 平常的网络流可以当做下界为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[ ...