2017-C18-team6

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 = 唐小虎 =

 Prelude: (？) 表示这种题目尚未出现过？

 - 关于上下界（费用流）（可行流）（最大流，最小流）（有无源汇）的一些想法
 - 上下界网络流中的super_S, super_T'''仅用來辅助流量平衡'''，当且仅当它们的流量满的时候'''才是可行流'''（流量平衡）
   - 非费用流
     - 无源汇
       - 仅求一个可行流，根据之前的分析，只要保证在建出super_S, super_T的情况下可以满流就能求出一个可行流
       - 最大（小）流（？）
     - 有源汇 
       - 仅求一个可行流，把源点汇点连起来（cap_low = 0, cap_max = inf），转成无源汇图判断。
       - 最大（小）流：二分cap_low（求最小流时二分cap_max），判断是否存在可行流（super_S, super_T连出的边满流）
   - 费用流（'''只要'''可行流的前提下最优化费用）
     - 无源汇：由于super_S，super_T的存在，每建一条边都会有两条辅助边帮助流量平衡，两条边中只要一条有费用即可，本来的边（cap_max-cap_min）当然也要加费用，然后在有super_S, super_T的图上强行跑sap就可以了。
     - 有源汇：把源汇连起来（cap_low = 0, cap_max = inf, cost = 0），转成无源汇图判断



 有无源汇的本质是什么？
 - 可能是circuit和path之间的区别
 - 最基本的建图其实只能解决circuit无费用是否存在可行流？
 - 有源汇为什么要把源汇连起来？
 - 转成circuit跑最小费用最大流
   - 最大流对应circuit合法，当然也就是path合法
   - 最小费用对应最小费用

如果哪里写错了请直接怼我。

唐小虎

Prelude: (？) 表示这种题目尚未出现过？

- 关于上下界（费用流）（可行流）（最大流，最小流）（有无源汇）的一些想法

- 上下界网络流中的super_S, super_T仅用來辅助流量平衡，当且仅当它们的流量满的时候才是可行流（流量平衡）

- 非费用流

- 无源汇

- 仅求一个可行流，根据之前的分析，只要保证在建出super_S, super_T的情况下可以满流就能求出一个可行流

- 最大（小）流（？）

- 有源汇

- 仅求一个可行流，把源点汇点连起来（cap_low = 0, cap_max = inf），转成无源汇图判断。

- 最大（小）流：二分cap_low（求最小流时二分cap_max），判断是否存在可行流（super_S, super_T连出的边满流）

- 费用流（只要可行流的前提下最优化费用）

- 无源汇：由于super_S，super_T的存在，每建一条边都会有两条辅助边帮助流量平衡，两条边中只要一条有费用即可，本来的边（cap_max-cap_min）当然也要加费用，然后在有super_S, super_T的图上强行跑sap就可以了。

- 有源汇：把源汇连起来（cap_low = 0, cap_max = inf, cost = 0），转成无源汇图判断

有无源汇的本质是什么？

- 可能是circuit和path之间的区别

- 最基本的建图其实只能解决circuit无费用是否存在可行流？

- 有源汇为什么要把源汇连起来？

- 转成circuit跑最小费用最大流

- 最大流对应circuit合法，当然也就是path合法

- 最小费用对应最小费用

如果哪里写错了请直接怼我。