使用 Dinic 跑的最大流

LOJ:116. 有源汇有上下界最大流

我的代码

我的AC记录

样例的图:

解释:

红色边:题目中给的边

绿色边:从(t(10)-->s(10))的虚拟边

粉色点:虚拟源点S(0)和虚拟汇点T(n+1)

粉色边:为保证流量守恒建的虚拟边

蓝/粉色数字:边的容量

发生问题:

在进行(S-->T)的第一遍Dinic后,求出的ans=43(跑满了所有紫边),但未更新相应的红边(如9-->1,9-->2),并且绿边的流量为40. 导致第二遍Dinic在计算(s-->t)的最大流时会重复计算某些边,使答案错误

进行了诡异处理:

在第一遍Dinic后将ans设置为绿边的流量,再进行第二遍Dinic即可通过该题??????

求dalao解释Qwq