求助:关于有源汇上下界最大流
  • 板块学术版
  • 楼主sunzz3183
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/4/26 20:57
  • 上次更新2024/4/29 04:34:43
查看原帖
求助:关于有源汇上下界最大流
171868
sunzz3183楼主2024/4/26 20:57

在求出 flow1flow1 之后,然后 ci=Ri−Li−f(i)c_i=R_i-L_i-f(i) 得到剩余容量,进行跑最大流,求出 flow2flow2,最后 ans=flow1+flow2ans=flow1+flow2。

为什么剩余容量一定不会增加,即求出新的最大流之后,f(i)f(i) 不会减少,使得最大流更大,求证明。

2024/4/26 20:57
加载中...