最小费用最大流类

orz hhw posted @ 2018年7月11日 13:44 in 算法学习 with tags 模板 费用流 算法学习 , 123 阅读

类型说明:基于CostEdge类,CostEdge类存储最大流中的边(x,y,nxt,cap,co),表示一条从x到y流量是cap费用是co的边,在邻接表中下一条边的标号是nxt。使用vector<CostEdge>来存储网络流中的边即可。

SPFA暴力增广

在有流量的边上按费用做SPFA,每次选最短路增广

SPFA多路增广

在有流量的边上按费用做SPFA,每次将最短路类似Dinic一起增广

ZKW费用流

标号并增广

Dijkstra费用流

用Dijkstra代替SPFA,第一次若有负权先做SPFA

消圈算法

求一个流量下的最小费用,将残量网络负权代价环消去,代码坑

代码