数字梯形
考虑网络流拆点。
对于一个点不能多次到达的限制，可以将其拆为两个点，中间容量为 \(1\)，权值为点的权值。然后由于点不重合那么边一定不重合，除了起点连下来的边容量为 \(1\)，其他边容量只要大于 \(1\) 就可以了。
第二个限制，不需要拆点，将费用放到边上，然后注意虚拟源点容量为 \(1\)、虚拟汇点容量为 INF（因为终点可能到达多次）。
第三个限制，除了虚拟源点容量为 \(1\)，其他都是 INF。
数字梯形
发布时间 2023-11-17 13:03:59作者: wscqwq