CF708D Incorrect Flow

在莫斯科国立大学网络机械学系研究生入学考试中，Sasha 被问及 Ford-Fulkerson 算法的问题。他对此了如指掌，因为在编程竞赛中多次使用过。作为题目，他被给出一个带有部分构建流的网络，要求他演示该算法的工作流程。他很快完成了书面部分，刚准备开始看题，才发现题目给出的网络不正确！ 假设给定一个有向图 $G(V,E)$，其中有两个特殊节点 $s$ 和 $t$，分别称为源点和汇点。记 $n$ 为图中的节点数，即 $n=|V|$，$m$ 表示图中的有向边数，即 $m=|E|$。在本题中规定节点 $1$ 总是源点，节点 $n$ 总是汇点。此外，对于每条边 $e$，定义容量函数 $c(e)$ 和流量函数 $f(e)$。如果满足以下条件，则 $f(e)$ 表示的是一个合法（正确）的流： 1. 对于每条边 $e$，流量为非负且不超过其容量，即 $0 \leq f(e) \leq c(e)$。 2. 对于每个既不是源点也不是汇点的节点 $v$（即 $v \ne s$ 且 $v \ne t$），其所有入边的流之和等于所有出边的流之和。换句话说，$v$ 处不会积存或消耗流量。 很明显，这道题是昨晚匆忙准备的，里面有不少错误。Sasha 向一位教授申请修正网络或者更换题目，但教授回复说研究生应当自己修正网络。为了不让题目变简单，教授要求 Sasha 以最小的修改次数修正网络。Sasha 不能移除边、添加新边或改变现有边的方向。他唯一能做的就是修改容量函数 $c(e)$ 和流量函数 $f(e)$。此外，所有数值仍需为非负整数。流是否为最大流没有要求。 请计算 Sasha 至少需要修改多少数值（即 $f(e)$ 和 $c(e)$）才能使流描述合法。总的修改量定义为绝对差值之和，设新函数为 $f^{*}(e)$ 和 $c^{*}(e)$，则总修改量为 $\sum_{e \in E} (|f^*(e) - f(e)| + |c^*(e) - c(e)|)$。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 100$，$0 \leq m \leq 100$）分别表示图中的节点数和有向边数。接下来的 $m$ 行中每行有四个整数 $u_i$、$v_i$、$c_i$ 和 $f_i$（$1 \leq u_i, v_i \leq n$，$u_i \ne v_i$，$0 \leq c_i, f_i \leq 1000000$），分别表示该边的起点编号、终点编号、当前容量和流量。 节点 $1$ 是源点，节点 $n$ 是汇点。保证没有任何边指向源点，也没有任何边从汇点出发。 图中不包含自环，但可能有重边。

输出一个整数，表示 Sasha 至少需要进行的总修改量，使流描述合法。

第一个样例中，流本身就是合法的。注意，流不是最大流，但题目没有要求最大流。 第二个样例中，唯一一条边的流量大于容量。有两种修正方法：要么将容量增至 $2$，要么将流量降为 $1$。 第三个样例中，节点 $2$ 的入流只有 $1$，而出流为 $2$。可以将第二条边的流量减少 $1$。 第四个样例中，存在一个孤立的流环，但按照定义这也是合法的。 由 ChatGPT 5 翻译