【bzoj1877】晨跑

题目大意

给出有$n$个点$m$条边的带权图

要求找到最多的(起点到终点)路径数且使总费用尽量少

路径与路径之间不能相交

建图

每个点只能经过一次

拆点，容量为$1$，费用为$0$

每条边有边权，且使得边权和最小

容量为$+∞$,费用为边权

源点和汇点

点$1$和点$n$可以经过多次，因此不用开超级源和超级汇，直接取点$1$和点$n$分别作为源点和汇点

阅读更多……

题目大意

给定一张$n$个点$m$条边的有向图，每条边都有一个容量$c$和一个扩容费用$w$（这里扩容费用是指将容量扩大$1$所需的费用）

询问

1. 在不扩容的情况下，$1$到$n$的最大流

2. 将$1$到$n$的最大流增加$k$所需的最小扩容费用

阅读更多……