这段代码是一个关于网络流问题的实现,使用了最小费用最大流算法(SPFA + 费用标号法)。主要解决的问题是如何安排每天的餐巾需求和清洗服务,使得总成本最小化。
主要结构和功能解析:
数据结构和变量定义:
使用了结构体 node 存储每条边的信息,包括起点、终点、流量、费用等。
last[] 数组用于存储每个节点的最后一条边的位置。
pre[] 数组记录最短路中的路径,pos[] 记录路径上的前驱节点。
dis[] 记录从起点到各节点的最短距离。
p[] 记录路径上的最小剩余容量。
图的构建:
ins() 函数用于向图中添加边,根据题目描述,构建了与餐巾相关的流网络。例如,从起点到每天晚上的脏餐巾节点,从每天白天的干净餐巾节点到汇点等。
SPFA算法:
spfa() 函数实现了单源最短路径算法(SPFA),用于找出从起点到汇点的最短路径,并计算路径上的最小剩余容量 p[] 和最短路径花费 dis[]。
最小费用最大流算法:
flow() 函数是主函数,通过多次调用 spfa() 函数来求解最小费用最大流问题,计算出总的最小成本。