模拟费用流 ​

核心思考方法 ​

增量 - 消圈法 ​

适用范围 ​

• 最小费用可行流
• 最小费用最大流：将连向汇点的边费用减 inf，转化为可行流

处理 ​

每次考虑加入新的点和边，新产生的：

1. 负圈
2. 源汇负路

模拟EK ​

适用范围 ​

很广

处理 ​

考虑每次新找一条最短增广路

常用结论 ​

增广路（负圈）不会重复经过同一节点

例题 ​

老鼠钻洞plus版：「ICPC World Finals 2018」征服世界 ​

solution ​

1. 首先建出费用流模型：类似上下界网络流，将两个权值相减跑最小费用最大流。
2. 考虑模拟费用流，先将最大流转可行流，增量法处理。
3. 考虑每次加入子树的根节点，每次只要看子树中的入流和出流（之前子树已经流尽了）。
4. 因为路径可以拆价值，所以直接匹配入和出就可以，结合可并堆实现即可。