关于有源汇上下界最小费用可行流
  • 板块学术版
  • 楼主TKXZ133
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/28 11:57
  • 上次更新2023/11/2 11:06:38
查看原帖
关于有源汇上下界最小费用可行流
767096
TKXZ133楼主2023/10/28 11:57

rt,为什么如下的建图用有源汇上下界最小费用可行流会错:

  • 从 SS 向所有点连流量为 [ai,ai][a_i,a_i],费用为 00 的边。
  • 点 ii 向点 i+1i+1 连流量为 [0,∞][0,\infty],费用为 11 的边。
  • 点 ii 向 TT 连流量为 [Li,Ri][L_i,R_i],费用为 00 的边。

用有源汇上下界最小费用可行流的建图后 SS 向所有点的流量都为 00,也就是说所有的 RiR_i 都会失效。

为什么?

2023/10/28 11:57
加载中...